CF1899E Queue Sort

CF1899E Queue Sort

题目链接)

题目大意

弗拉德找到了一个由 $n$ 个整数组成的数组 $a$ ，并决定按不递减的顺序排序

为此，弗拉德可以多次执行下面的操作：

• 提取数组的第一个元素，并将其插入末尾；
• 将之前的元素与前一个元素对调，直到它成为第一个元素或严格大于前一个元素

对于一个操作，必须应用这两个操作

例如，如果对数组$ [ 4, 3, 1, 2, 6, 4 ]$执行操作，它将发生如下变化：

• $[ \color{red}{4}, 3, 1, 2, 6, 4 ];$
• $[ 3, 1, 2, 6, 4, \color{red}{4} ];$
• $[ 3, 1, 2, 6, \color{red}{4}, 4 ];$
• $[ 3, 1, 2, \color{red}{4}, 6, 4 ].$

求对数组进行排序所需的最少操作数，不可能输出 $-1$

思路

容易看出，当数组的第一个元素为整个数组的最小元素时，再次对数组进行操作无任何效果

所以我们只需要判断数组中最小的元素在原数组位置之后的单调性即可

对于一个数组有多个最小值的情况，只需要分析最早出现的那个最小值即可

最终答案就是最小值之前的元素个数

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=2e5+1;
int awa[maxn];
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read(),minn=1e10,wz=1;
        for(int i=1;i<=n;i++)
        {
            awa[i]=read();
            if(minn>awa[i]) minn=awa[i],wz=i;
        }
        int f=0;
        for(int i=wz+1;i<=n;i++)
        {
            if(awa[i]<awa[i-1]) {f=1;break;}
        }
        if(f) puts("-1");
        else write(wz-1),puts("");
    }
    return _123hh2;
}