题解：CF1899E Queue Sort

lailai0916 · 2023-11-19 18:19:06 · 题解

解题思路

对非最小元素进行操作，都会将该元素在数列中排序。

设数列中最小的元素值为 m，考虑无解情况：

• 当第一个 m 到达最左边时，且数列不是有序的，那么 x 会移动到最右边。
• 但由于 x 是最小的元素，又会一直向左移动到最左边，形成死循环。

所以在第一个 m 到达最左边时，数组有序，才会有解。

操作次数为开始时第一个 m 前面的元素个数。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=200005;
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        int k=1;
        for(int i=1;i<=n;i++)if(a[i]<a[k])k=i;
        cout<<(is_sorted(a+k,a+n+1)?k-1:-1)<<'\n';
    }
    return 0;
}