本文主要是介绍Codeforces Div. 2 #259-B. Little Pony and Sort by Shift，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
//AC代码
/*
题意：给你一个无序数列（长度为n）
执行操作：把最后一个元素放在第一个位置，其他元素向后挪一个位置
问执行几次这样的操作使得数列递增（注意不是严格递增元素相等也算递增）
此题想一想就知道只要是符合条件的数列那么只可能存在两个递增子序列并且后一个子序列所有元素不能大于前一个子序列的第一个元素
*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
#define LL long long
#define IT __int64
#define zero(x) fabs(x)<eps
#define mm(a,b) memset(a,b,sizeof(a))
const int INF=0x7fffffff;
const double inf=1e8;
const double eps=1e-10;
const double PI=acos(-1.0);
const int Max=200001;
using namespace std;
int s[Max],k[Max],t[Max];
int main()
{
int n,m,i,j,p,h;
while(cin>>n)
{
for(i=0;i<n;i++)
cin>>s[i];
if(n<=3)
{
if(n==1)
cout<<0<<endl;
else if(n==2)
{
if(s[0]<=s[1])
cout<<0<<endl;
else
cout<<1<<endl;
}
else if(n==3)
{
p=1;
for(i=1;i<n;i++)
{
if(s[i]>=s[i-1])
p+=1;
}
if(p==n)//全部递增
cout<<0<<endl;
else if(p==1)
cout<<-1<<endl;//全部递减
else
{
if(s[1]<s[2]&&s[1]<s[0])
{
if(s[2]>s[0])
cout<<-1<<endl;
else
cout<<2<<endl;
}
if(s[1]>s[2]&&s[1]>s[0])
{
if(s[2]>s[0])
cout<<-1<<endl;
else
cout<<1<<endl;
}
}
}
}
else
{
p=1;
for(i=1;i<n;i++)
{
if(s[i]>=s[i-1])
p+=1;
}
if(p==n)//全部递增
{
cout<<0<<endl;
}
else if(p==1)//全部递减
{
cout<<-1<<endl;
}
else
{
k[0]=s[0];
m=1;
for(;m<n;m++)
{
if(s[m]<s[m-1])
break;
else
k[m]=s[m];
}
t[0]=s[m];
h=1;
for(i=m+1;i<n;i++)
{
if(s[i]<s[i-1])
break;
else
t[h++]=s[i];
}
if((h+m)!=n)//不止两个递增子序列，或者一个递增（递减）另一个递减（递增）
cout<<-1<<endl;
else
{
p=0;
for(i=0;i<h;i++)
{
if(t[i]>k[0])
{
p=1;
break;
}
}
if(p==1)
cout<<-1<<endl;
else
cout<<h<<endl;
}
}
}
}
return 0;
}
/*
2
2 1
3
1 3 2
2
1 2
5
1 2 3 4 0
5
5 1 2 3 4
7
60 100 120 13 15 55 61
7
60 100 120 13 15 55 59
*/
这篇关于Codeforces Div. 2 #259-B. Little Pony and Sort by Shift的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
