自动搬运

查看原文

来自洛谷，原作者为

	巨型方块 **

搬运于2025-08-24 21:23:48，当前版本为作者最后更新于2017-07-15 13:45:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

直接o（n）扫过去；

遇到不对的就直接交换就好了；

因为每个东西迟早要到自己的位置上的；

应该不会被hack把

#include<bits/stdc++.h>
#define Ll long long
using namespace std;
const int N=1e5+5;
map<int,int>F;
int a[N],b[N];
int n,m,ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i],F[a[i]]=i;
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        if(a[i]!=b[i]){
            ans++;
            int x=F[b[i]];
            F[a[i]]=x;
            a[x]=a[i];
        }
    printf("%d",ans);
}