P8637

Maysoul · 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;
}