C++, Сортировка вставками

Question

C++, Сортировка вставками

Я не знаю что написать Ведьмин Ученик (159), на голосовании 11 месяцев назад

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

Ввод:
5 3
Вывод:
1 5 2 3 4

Answer 1

Василий Знаток (499) 1 год назад

#include <iostream>
#include <vector>

std::vector<int> getPermutationWithSwaps(int n, int k) {
std::vector<int> arr(n);
for (int i = 0; i < n; ++i) {
arr[i] = i + 1;
}

for (int i = 0; i < k; ++i) {
std::swap(arr[n - 2 - i], arr[n - 1 - i]);
}

return arr;
}

int main() {
int n, k;
std::cin >> n >> k;

std::vector<int> result = getPermutationWithSwaps(n, k);

for (int x : result) {
std::cout << x << " ";
}
std::cout << std::endl;

return 0;
}

Я не знаю что написать ВедьминУченик (159) 1 год назад

Использует слишком много памяти, можно ли оптимизировать?

Василий Знаток (499) Я не знаю что написать Ведьмин, #include <iostream> #include <vector> int main() { int n, k; std::cin >> n >> k; std::vector<int> arr(n); for (int i = 0; i < n; ++i) { arr[i] = i + 1; } for (int i = 0; i < k; ++i) { std::swap(arr[n - 2 - i], arr[n - 1 - i]); } for (int i = 0; i < n; ++i) { std::cout << arr[i] << " "; } std::cout << std::endl; return 0; } // Производим k обменов for (int i = 0; i < k; ++i) { std::swap(arr[n - 2 - i], arr[n - 1 - i]); } // Выводим элементы перестановки for (int i = 0; i < n; ++i) { std::cout << arr[i] << " "; } std::cout << std::endl; return 0; }