CF1455D Solution

题目链接

题解

可以发现，如果(a_i>x)且不对(a_i)执行操作，(a_{i+1}-a_n)便无法执行操作。这个性质可以保证下述方法的正确性与最优性：

找到第一个满足(a_{pos})之后序列单调不降的(pos)，依次对所有(1le ile pos)且(a_i>x)的元素将(x)与(a_i)互换。因为(x)在操作过程中始终是单调递增的，因此所有进行过操作的元素一定满足单调不降。如果遇到(a_i<a_{i-1})的情况，则判定无法实现，因为(a_{i-1})已经是满足单调递增情况下的最小值。如果所有(1le ile pos)全部执行完毕，但是(a_{pos}>a_{pos+1})也判定无法实现，因为此时一定(x<a_{pos}<a_{pos+1})，无法进行后续操作。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=510,inf=0x3f3f3f3f;
int a[N]; 
int main()
{
	int t,n,x;
	scanf("%d",&t);
	while(t--)
	{
		int ans=0,pos=0; 
		bool flag=0;
		scanf("%d%d",&n,&x);
		for(int i=1;i<=n;i++) 
		{
			scanf("%d",&a[i]); 
			if(a[i]<a[i-1]) pos=i;
		}
		for(int i=1;i<pos;i++)
		{
			if(a[i]>x) {ans++; swap(a[i],x);}
			else if(a[i]<a[i-1]) {flag=1; break;}
		}
		if(a[pos-1]>a[pos] || flag) printf("-1
");
		else printf("%d
",ans);
	}
	return 0;
}