1067. Sort with Swap(0,*) (25)-PAT甲级真题

逆向思维，错位可以想象成链表“错位链”，我们就需要寻找类似"a→b,b→c,c→a"这样的结构，因为这样能一次性换对最多的元素。每一个长度为n的链如果不包含0，则需要n+1次交换，包含则需要n-1次，而0最多只会加入一个链中，所以可以最后考虑

#include<bits/stdc++.h>
using namespace std;
int main(){int n,idx,cnt=0;scanf("%d",&n);vector<int> a(n);vector<bool> wrong(n,false);for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]!=i)wrong[i]=true;}for(int i=0;i<n;i++){if(wrong[i]){wrong[i]=false;int next=a[i];cnt++;while(wrong[next]){wrong[next]=false;next=a[next];cnt++;}cnt++;}}if(a[0]!=0) cnt-=2;printf("%d",cnt);
}