【PAT甲级】1067 Sort with Swap(0, i) (25 分)

题意：

输入一个正整数N（<=100000），接着输入N个正整数（0~N-1的排列）。每次操作可以将0和另一个数的位置进行交换，输出最少操作次数使得排列为升序。

AAAAAccepted code：

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[100007],b[100007];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    int ans=n-1;
    for(int i=0;i<n;++i){
        cin>>a[i];
        b[a[i]]=i;
        if(a[i]==i&&a[i])
            --ans;
    }
    int sum=0;
    int pos=1;
    while(ans)
        if(b[0]!=0){
            swap(b[0],b[b[0]]);
            ++sum;
            --ans;
        }
        else
            for(int i=pos;i<n;++i)
                if(b[i]!=i){
                    swap(b[0],b[i]);
                    ++sum;
                    pos=i+1;
                    break;
                }
    cout<<sum;
    return 0;
}