Задача на антипузырек

Question

Ровно К обменов

Даны два числа n и k.

Выведите перестановку из n чисел (n чисел от 1 до n без повторений) такую, чтобы сортировка пузырьком по возрастанию на соответствующем массиве сделала ровно k обменов. Если возможных ответов несколько — выведите любой.

Выведите искомую перестановку в одной строке. Числа разделяйте пробелами.

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

#include <iostream>
using namespace std;

int main() {
    const int max_size = 100;

    int arr[max_size];
    int size, swap_need;
    cin >> size >> swap_need;

    // генерация чисел
    for (int i = 0; i < size; i++) {
        arr[i] = i + 1;
    }

    int swaps_now = 0, m = 0;
    

    // пока текущее количество swap'ов != нужному
    while (swaps_now != swap_need) {
        if (m + 1 >= size) m = 0;

        /* m нужно для отслеживания выхода за границу,
        т.е если мы выходим за границу, то просто
        начинаем менять с начала */

        swap(arr[m], arr[m + 1]);
        m++;

        // копия массива для сортировки
        int new_arr[max_size];
        for (int p = 0; p < size; p++) {
            new_arr[p] = arr[p];
        }

        // подсчет количества swap'ов в пузырьке 
        swaps_now = 0;
        for (int i = 1; i < size; i++) {
            for (int j = 1; j <= size - i; j++) {
                if (new_arr[j - 1] > new_arr[j]) {
                    swap(new_arr[j - 1], new_arr[j]);
                    swaps_now++;
                }
            }
        }
    }

    // вывод массива
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

Answer 1

Я не знаю ограничений, но попробуйте вот этот код:

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);

const int max_size = 100;
int arr[max_size];
int size, swap_need;
cin >> size >> swap_need;

for (int i = 0; i < size; ++i)
    arr[i] = i + 1;

int swap_now = 0;
int k = 0;
bool isHas = false;
if (swap_need != 0) {
    for (int m = 0; m < size * size; ++m) {
        for (int i = size - 1; i > k; --i) {
            swap(arr[i], arr[i - 1]);
            ++swap_now;
            if (swap_now == swap_need) {
                isHas = true;
                break;
            }
        }
        ++k;
        if (isHas) break;
    }
}

for (int i = 0; i < size; ++i)
    cout << arr[i] << " ";
cout << endl;

return 0;
}

Если он пройдет, то я опишу как он работает. Только отпишите мне об этом.

А так оказывается объяснение есть уже тут.

Алгоритм, который приведен выше работает за O(n^2) времени. Ниже алгоритм работающий за O(n) времени.

int main() {
const int max_size = 100;
int arr[max_size];
int size, swap_need;
cin >> size >> swap_need;

int n = size;
int j = 1;
for (int i = n; i > 0; --i) {
    if (swap_need == 0 && (j + i) == i)
        break;
    if (swap_need >= i - 1) {
        swap_need -= (i - 1);
        arr[size - i] = n--;
    }
    else arr[size - i] = j++;
}

for (int i = 0; i < size; ++i)
    cout << arr[i] << " ";

}

Если посмотреть на то, как числа передвигаются справа налево (лесенкой вниз или спиралью). То есть если swap_need будет больше 3, то первая цифра всегда будет 5. Если swap_need будет больше 6 то вторая цифра будет всегда 4. Больше 8 то будет третьей цифрой 3. Больше 9 то 2, ну и единица. Надеюсь объяснил принцип.

Answer 2

На основе ответа @MBo на этот вопрос было сделано решение на C++

#include <iostream>
using namespace std;

int main() {
    const int max_size = 100;

    int a[max_size];
    int size, swap_need;
    cin >> size >> swap_need;

    int n = size;
    int now = 0;
    while (size > 0) {
        if (swap_need > size - 1) {
            a[now] = size;
            swap_need -= (size - 1);
            size--;
            now++;
        }
        else {
            for (int i = 1; i < size - swap_need; i++) {
                a[now] = i;
                now++;
            }
            a[now] = size;
            now++;
            for (int i = size - swap_need; i < size; i++) {
                a[now] = i;
                now++;
            }
            swap_need = 0, size = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }

    return 0;
}

БЛОГ НА HUSL

Задача на антипузырек

Ответы (2 шт):