CF1455D

Solution:

这题很容易想到，如果想让序列变得有序，那么不管怎么样你肯定需要把前面比后面大的的位置记录下来，这里只需要记录最后一个位置。此时我们就可以从 \(1\) 遍历到我们记录的最后位置，如果这里的 \(a[i]\) 大于 \(x\) 那么我们就需要交换这两个数。当然最后还需要检查一遍，如果最终还是没有让这个序列有序，那么我们就直接输出 \(-1\) 即可。当然这样做的正确性显而易见这里就不多提了。

Code:

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<‘0‘ || c>‘9‘){if(c==‘-‘) f=0;c=getchar();}
    while(c>=‘0‘ && c<=‘9‘) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?x:-x;
}
int T,n,x,a[510],pos,ans,f;
signed main()
{
    T=read();
    while(T--)
    {
        n=read(),x=read();
        pos=ans=f=0;
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            if(a[i]<a[i-1]) pos=i;
        }
        for(int i=1;i<=pos;i++)
            if(a[i]>x){swap(a[i],x);ans++;}
        for(int i=1;i<=n;i++)
        {
            if(a[i]<a[i-1])
            {
                puts("-1");
                f=1; break;
            }
        }
        if(!f) printf("%d\n",ans);
    }
    return 0;
}

CF1455D

原文：https://www.cnblogs.com/ForeverOIer/p/14169946.html