首页 > 代码库 > Codeforces Round #259 (Div. 2) （序列）

Codeforces Round #259 (Div. 2) （序列）

2024-07-15 11:52:03   222人阅读

题目链接：http://codeforces.com/contest/454/problem/B


B. Little Pony and Sort by Shift
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, Twilight Sparkle is interested in how to sort a sequence of integers a1,?a2,?...,?an in non-decreasing order. Being a young unicorn, the only operation she can perform is a unit shift. That is, she can move the last element of the sequence to its beginning:

a1,?a2,?...,?an?→?an,?a1,?a2,?...,?an?-?1.

Help Twilight Sparkle to calculate: what is the minimum number of operations that she needs to sort the sequence?

Input

The first line contains an integer n (2?≤?n?≤?105). The second line contains n integer numbers a1,?a2,?...,?an (1?≤?ai?≤?105).

Output

If it‘s impossible to sort the sequence output -1. Otherwise output the minimum number of operations Twilight Sparkle needs to sort it.

Sample test(s)
input
2
2 1
output
1
input
3
1 3 2
output
-1
input
2
1 2
output
0

思路：

判断有存在几个“下坡”，也就是后面的数比前面的小；

如果没有则输出0；如果有不止一个，则输出-1；如果恰有一个， 那么就需要判断a[1]和a[n]的大小关系；


代码如下：

#include <cstdio>
#include <cstring>
int main()
{
	int n;
	int i, j;
	int a[100017];
	while(~scanf("%d",&n))
	{
		for(i = 1; i <= n; i++)
		{
			scanf("%d",&a[i]);
		}
		int cont = 0;
		int t;
		for(i = 2; i <= n; i++)
		{
			if(a[i] < a[i-1])
			{
				cont++;
				t = i;
			}
		}
		if(cont == 0)
			printf("0\n");
		else if(cont > 1)
			printf("-1\n");
		else if(cont == 1 && a[n] <= a[1])
			printf("%d\n",n-t+1);
		else
			printf("-1\n");
	}
	return 0;
}


联系
我们