Поиск минимального лексикографического массива

Question

Я попытался решить этот вопрос для интервью. Мой код работает для тестовых случаев, но не подходит для всех реальных тестовых случаев ввода. Я очень старался найти ошибку, но не смог этого сделать. Пожалуйста, найдите мой код под вопросом

Боб любит сортировать очень много. Он всегда думает о новых способах сортировки массива. Его друг Рам дает ему сложную задачу. Он дает Бобу массив и целое число К. Задача состоит в том, чтобы создать лексикографический минимальный массив после не более K-свопов. Только последовательные пары элементов могут быть заменены. Помогите Бобу вернуть минимальный возможный лексикографический массив после не более K-свопов.

Ввод: первая строка содержит целое число T т. Е. Количество тестовых примеров. T тестовые примеры. Каждый тест имеет 2 строки. Первая строка содержит N(number of elements in array) и K(number of swaps). Вторая строка содержит n целые числа массива.

Выход: Распечатайте минимальный лексикографический массив.

Ограничения:

1 <= T <= l0 

1 <= N,K <= 1000 

1 <= A[i] <= 1000000 

Пример ввода (ссылка) Plaintext

2 

3 2 

5 3 1 

5 3 

8 9 11 2 1 

Пример вывода (Plaintext Ссылка)

1 5 3 

2 8 9 11 1 

Объяснение

После обмена 1:

5 1 3 

После замены 2:

1 5 3 

{1,5,3} лексикографически минимальна, чем {5,1,3}

Пример 2:

Сменный 1: 8 9 2 11 1

своп 2: 8 2 9 11 1

Замена 3: 2 8 9 11 1

#include <iostream> 
    using namespace std; 

    void trySwap(int a[], int start, int end, int *rem) 
    { 
//cout << start << " " << end << " " << *rem << endl; 
    while (*rem != 0 && end > start) 
    { 
    if (a[end - 1] > a[end]) 
    { 
     swap(a[end - 1], a[end]); 
     (*rem)--; 
     end--; 
    } 
    else end--; 
} 
} 

void getMinimalLexicographicArray(int a[], int size, int k) 
{ 
int start , rem = k, window = k; 

for (start = 0; start < size; start++) 
{ 
    window = rem; 
    if (rem == 0) 
     return; 
    else 
    { 
     //cout << start << " " << rem << endl; 
     int end = start + window; 
     if (end >= size) 
     { 
      end = size - 1; 
     } 
     trySwap(a, start, end, &rem); 
    } 
} 
} 

int main() 
{ 
int T, N, K; 
int a[1000]; 
int i, j; 

cin >> T; 
for (i = 0; i < T; i++) 
{ 
    cin >> N; 
    cin >> K; 

    for (j = 0; j < N; j++) 
    { 
     cin >> a[j]; 
    } 

    getMinimalLexicographicArray(a, N, K); 

    for (j = 0; j < N; j++) 
     cout << a[j] << " "; 
    cout << endl; 

} 

return 0; 

} 

Answer 1

Вот два неудачных тестов.

2 

2 2 
2 1 

5 3 
3 2 1 5 4 

В первом, ваш код не делает свопы, потому что K> = N. Во втором, ваш код свопы 5 и 4, когда он должен провести свой третий обмен на 3 и 2.

EDIT : новая версия все еще слишком жадна.Правильный выход для

1 

10 10 
5 4 3 2 1 10 9 8 7 6 

является

1 2 3 4 5 10 9 8 7 6 

.