自动搬运

查看原文

来自洛谷，原作者为

	良心WA题人 啦叭叭叭 啾啾啾啦叭叭叭

搬运于2025-08-24 22:55:14，当前版本为作者最后更新于2024-01-13 20:25:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，$a_n\not=n$ 无解。

对于操作过程，考虑一种方案：

从大到小枚举 $i$

• 若 $p_i\not=i$ 则操作使得 $p_j=i$ 的 $j$。

尝试证明上述算法的正确性。显然经过上述操作后可以完成排序。而每次操作将会把序列变为：

$1,2,3\dots j-1,j+1\dots j,i,i+1\dots n$

若之前操作 $1$ 到 $j-1$ 中的数，则必然不会跨过 $j$，则在 $j$ 操作后必然还需要再进行操作。

若之前操作了 $j+1$ 到 $i-1$ 中的数，则先操作 $j$ 再操作这中间的数对答案没有影响。

上述操作按理来讲可以通过一些数据结构直接维护。但是这显然太麻烦了。考虑去观察哪些情况下 $i$ 不会被操作，可以发现 $i$ 不被操作当且仅当 $p_i$ 为 $i$ 开始的后缀的最小值。

证明比较简单，首先若中间存在小于 $p_i$ 的数则 $i$ 必然比这个数先操作，那么相对位置不会变化，则 $i$ 后面不可能为 $i+1$ 到 $n$ 这些全都比它大的数。

而若不存在，则任何比 $p_i$ 小的数无法到 $p_i$ 后方，所以当 $p_i$ 操作时右侧均比 $p_i$ 大，显然满足要求。故得证。

#include<bits/stdc++.h>
using namespace std;
const int NN=2e6+4;
int a[NN];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	if(a[n]!=n)
	{
		printf("-1");
		return 0;
	}
	int minn=1e9,ans=0;
	for(int i=n;i>=1;i--)
	{
		if(a[i]<minn)
			minn=a[i];
		else
			ans++;
	}
	printf("%d",ans);
	return 0;
}