首页 > 代码库 > Codeforces Round #259 (Div. 2) (序列)
Codeforces Round #259 (Div. 2) (序列)
题目链接:http://codeforces.com/contest/454/problem/B
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:
Help Twilight Sparkle to calculate: what is the minimum number of operations that she needs to sort the sequence?
The first line contains an integer n (2?≤?n?≤?105). The second line contains n integer numbers a1,?a2,?...,?an (1?≤?ai?≤?105).
If it‘s impossible to sort the sequence output -1. Otherwise output the minimum number of operations Twilight Sparkle needs to sort it.
2 2 1
1
3 1 3 2
-1
2 1 2
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; }