Решение задачи Маленькая пони и сортировка сдвигами с Codeforces

Без пояснения   Просмотров: 18


Как-то раз Twilight Sparkle захотела отсортировать последовательность целых чисел a 1, a 2, ..., a n в неубывающем порядке. Будучи молодым единорогом, Twilight Sparkle умеет выполнять лишь одно действие — единичный сдвиг. Другими словами, она может переместить последний элемент последовательности в начало:

a 1, a 2, ..., a n → a n, a 1, a 2, ..., a n - 1.
Какое минимальное количество действий понадобится Twilight Sparkle, чтобы отсортировать последовательность по неубыванию?

Код

#include<bits/stdc++.h>
using namespace std;
int n,m,a[300000],p;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		if(a[i%n]<a[i-1])
		{
			m++;
			p=i;
		}
	}
	if(m==0)
		cout<<0;
	else if(m<2)
	{
		cout<<n-p;
	}
	else
		cout<<-1;
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться