codeforce 259B 第二场最新题解 (找规律)

男娘i 2022-08-10 15:52 190阅读 0赞

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 *a*1, *a*2, ..., *a**n* 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:

*a*1, *a*2, ..., *a**n* → *a**n*, *a*1, *a*2, ..., *a**n* - 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 *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 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

input

3
    1 3 2

output

-1

input

2
    1 2

output

/*codefoce 259B
    这道题主要还是找规律吧，就是自己多模拟一些事例会发现这样的规律：
    就是扫过去，开始严格递增，后来又递减，就是从由递增到递减的变化的位置+1开始数起，
    如果以后全是递增把其个数累加起来会发现就是需要的最小移动的步数，
    若后面不是严格递增的就输出-1；规律题就是这样，找到了代码实现很简单的
    具体是实现见代码：
    如有bug请各位大神指出，菜鸟不胜感激。 
    */
    # include<iostream>
    # include<cstdio>
    # include<cstring>
    # include<cstdlib>
    # include<algorithm>
    # include<cmath>
    int s[100005];
    using namespace std;
    int n,t,ans,i;
    int main()
    {
    	while(cin>>n)
    	{
    		ans=0;
    		for(i=0;i<n;i++)
    		{
    			cin>>s[i];
    		}
    		for(i=0;i<n;i++)
    		{
    			if(s[i]>s[i+1]) 
    			{
    			  t=i;
    		      break;	
    			}
    		}
    		for(i=t+1;i<n;i++)
    		{
    			if(s[i]<=s[(i+1)%n]) ans++;
    			else break;
    		}
    	 if(i==n) cout<<ans<<endl;
    	 if(i<n)cout<<-1<<endl;
    	}
    	return 0;
    }