Решение задачи №392 «Сдвиг перестановки» с ACMP





Решение задачи №392 «Сдвиг перестановки» с ACMP

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

Перестановкой порядка n называется последовательность из попарно различных целых положительных чисел p1, p2, ... , pn, где каждое 1 ≤ pi ≤ n. Будем говорить, что перестановка q1, q2, ... , qn лексикографически меньше перестановки p1, p2, . . . , pn, если существует такое i, что qi < pi, а для любого j < i pj = qj .

Циклическим сдвигом на k перестановки p1, p2, ... , pn называется последовательность, pk+1, pk+2, ... , pn, p1, ... , pk. Отметим, что любой циклический сдвиг перестановки также является перестановкой.

Ваша задача состоит в том, чтобы найти наименьший лексикографически циклический сдвиг заданной перестановки.

Входные данные
Первая строка входного файла INPUT.TXT содержит порядок n (1 ≤ n ≤ 105) заданной перестановки. Вторая строка содержит числа p1, p2, ... , pn, отделенные друг от друга пробелами.

Выходные данные
В выходной файл OUTPUT.TXT выведите перестановку, являющуюся наименьшим лексикографически циклическим сдвигом перестановки, заданной во входном файле.

#include<iostream>
using namespace std;
main()
{
int a[100000],i,n,k,m=0;
cin>>n;

for(i=0;i<n;i++)
{
cin>>a[i];
if(a[i]<a[m])m=i;}
for(i=m;i<n;i++)cout<<a[i]<<' ';
for(i=0;i<m;i++)cout<<a[i]<<' ';
}



Условия задач взяты с сайта acmp.ru