E 交换题解

我的想法，找出每个环的边数-1，再累加起来，需要map.

#include<bits/stdc++.h>
using namespace std;
int ans;
bool cmp(int a,int b){
    return a<b;
}

int main(){
    int n,ans=0;
    cin>>n;
    int a[100005],b[100005];
    map<int,int> mp;
    for(int i=0;i<n;++i) {scanf("%d",&a[i]);b[i]=a[i];}
    sort(b,b+n,cmp); 
    for(int i=0;i<n;++i) mp[b[i]]=i;
    for(int i=0;i<n;++i){
        if(mp[a[i]]!=i)
        {int p=mp[a[i]];
        ++ans;
        while(mp[a[p]]!=i){
            ++ans;
            int q=p;
            p=mp[a[p]];
            mp[a[q]]=q;//环中遍历过的元素需要修改位置记录
        }
        mp[a[p]]=p;
        }
    }
    printf("%d\n",ans);
    return 0;
}