自动搬运

查看原文

来自洛谷，原作者为

	ikunTLE 互关条件见主页（luogu.me/paste/1ij66blw），关注我可以获得我小号 OIerDb 的关注（需私信） || 最后在线时间：2025年8月24日21时26分

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

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

以下是正文

题目传送门

思路

令 $b$ 为排序后的 $a$。分为 $2$ 种情况：

• 若 $a_i=b_i$，那么无需交换。
• 若 $a_i\neq b_i$，则需要将正确答案交换到 $i$ 的位置上，即多了一次交换。

由于最后一个数交换后会回到正确的位置，所以答案需要 $-1$。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=105;
int a[N],b[N];
int main(){
	int n=read();
	for(int i=1;i<=n;++i)
		a[i]=b[i]=read();
	sort(b+1,b+n+1);
	int ans=-1;
	for(int i=1;i<=n;++i)
		ans+=(a[i]!=b[i]);
	printf("%d\n",ans);
	return 0;
}