e-olymp 2386. Следующая перестановка

Условие задачи

Найдите следующую перестановку. Тождественная перестановка является следующей для обратной.

Входные данные

В первой строке записано количество элементов $n$ $\left(1\leqslant n\leqslant10^5\right)$ в перестановке. Во второй строке записана перестановка из $n$ чисел.

Выходные данные

Вывести $n$ чисел — искомую перестановку.

Тесты

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

Алгоритм Нарайаны

Код программы

Решение

Пусть $a$ — данная $n$-элементная перестановка $\left(a\;=\;\left[a_1,\;a_2,\;…,\;a_n\right]\right)$. Применяем алгоритм Нарайаны :

  • Находим наибольший номер $i$ (если он существует), такой, что $a_i<a_{i+1}$. Находим такой номер $j$, что число $a_j$ является наименьшим среди чисел $a_{i+1},\;a_{i+2},\;…,\;a_n$, превосходящим $a_j$. Меняем местами элементы $a_i$ и $a_j$ .
  • Если такого номера не существует, то $a$ — наибольшая $n$-элементная перестановка.
  • Изменяем порядок элементов, занимающих места с $\left(i+1\right)$-го по $n$-е, на противоположный.

Полученная перестановка $\left[a_1,\;a_2,\;…,\;a_{i-1},\;a_j,\;a_n,\;a_{n-1},\;…,\;a_{j+1},\;a_i,\;a_{j-1},\;…,\;a_{i+1}\right]$  будет являться искомой перестановкой.

Ссылки

 Функция next_permutation()

Код программы

Решение

Применяем функцию next_permutation() , которая генерирует следующую лексиграфическую перестановку в диапазоне элементов.

Ссылки