自动搬运

查看原文

来自洛谷，原作者为

	Maysoul AFO(2023/3/15——2023/11/19)

搬运于2025-08-24 22:40:57，当前版本为作者最后更新于2023-04-22 10:16:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路：

用贪心的思路去思考问题：

当当前瓶子不在正确的位置上时，那么它正确的位置上是否也是不正确的？

比方说在教室里，小明占了你的座，那你肯定没法坐在你自己的座位上。

这一特性，足以说明贪心思路的正确性。

因为它不会打乱正确顺序的瓶子。

那我们只需要把它枚举一遍，遇到不正确的就交换不就好了吗？

for (int i=1;i<=n;i++)
{
	if(a[i]!=i)
	{
		swap(a[i],a[a[i]]);
		ans++;
	}
}	

像这样，就完成了对瓶子的初步交换。

但是换一遍的话，肯定会有瓶子被调换到了错误的位置。

那我们考虑最坏的结果，无非就是所有瓶子都不在正确的位置上。

所以持续进行 $n$ 次这样的循环，就可以确保所有瓶子都在正确的位置上。

AC CODE：

//2023/4/22
//别着急，先通读一遍题目
//别忘了开long long
//写完先看一遍怎么降复杂度
//要么开全局变量要么给定初值
//想想看，有什么情况需要特判
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int num,ans;
int a[10010];
int main()
{
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for (int j=1;j<=n;j++)
	{
		for (int i=1;i<=n;i++)
		{
			if(a[i]!=i)
			{
				swap(a[i],a[a[i]]);
				ans++;
			}
		}	
	}
	cout<<ans<<endl;
	return 0;
}