Link

CF1899 E Queue Sort

Question

给出一个序列 \(\{a\}\) ，可以进行一种操作：把第一个数放到最后，然后向前移，直到前面的那个数比它小为止

求把序列变成非降序列的次数

Solution

先来考虑无法变成非降序列的情况

如果第一个数最小，在一次操作后，第一个数还会回到第一个数，就卡死了

所以，如果第一个数后面存在一个 \(a[i]>a[i+1]\) 就无法变成非降序列了

然后考虑次数，由于在最小值前的所有数都要移动到最小值后面，所以移动的次数就是最小值前面数的个数

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,INF=2e9;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int a[maxn];
void solve(){
    int N=read();
    for(int i=1;i<=N;i++) a[i]=read();
    int Min=a[1],Min_i=1;
    for(int i=2;i<=N;i++){
        if(Min>a[i]) {Min=a[i];Min_i=i;}
    }
    for(int i=Min_i;i<N;i++){
        if(a[i]>a[i+1]) {printf("-1\n");return ;}
    }
    printf("%d\n",Min_i-1);
    return ;
}
int main(){
    // freopen("E.in","r",stdin);
    int T=read();
    while(T--)solve();
    return 0;
}