题解：CF1899E Queue Sort

原题链接

• 洛谷 CF1899E Queue Sort

解题思路

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

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

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

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

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

参考代码

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

const int inf=0x3f3f3f3f;
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;
			}
		}
		if(is_sorted(a+k,a+n+1))
		{
			cout<<k-1<<'\n';
		}
		else
		{
			cout<<"-1"<<'\n';
		}
	}
	return 0;
}