PAT甲级1067.

目录

A1067

题目

样例

输入:

10
3 5 7 2 6 4 9 0 8 1

输出:

9

思路和坑点

　　表排序。给出的序列，由若干个环组成。由于和0交换，因此根据环的特征分三类：

• 单独一个元素构成一个环，即自己在自己的位置上，不需要交换，交换次数为0
  
• 包含0的环，这样的环只和0交换，假设环中有n个元素，则需要交换n-1次
  
• 不包含0的换，由于只能和0交换，因此将任意一个环中的元素和0交换，将其纳入环中再进行交换，假设环中有n个元素，则需要n+1次交换
  

　　具体的解释参见代码注释或者参考MOOC陈越姥姥的讲解swap(0,*)

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,ans=0;
    cin>>n;
    vector<int> v(n);                    //存储数据 
    vector<bool> vis(n,false);            //访问标记 
    for(int i=0;i<n;i++){                //读取输入 
        cin>>v[i];
    } 
    for(int i=0;i<n;i++){                //遍历数组，统计环，并计算 
        if(vis[i]==false){
            int flag=0,cnt=0,k=i;        //flag表示有没有0，如果是0表示没有，否则表示有，cnt统计环中元素个数 
            while(vis[k]==false){        //使用k做指针，遍历环并标记环上的元素为已访问 
                if(v[k]==0) flag=1;
                vis[k]=true; cnt++;        //统计环上元素个数 
                k=v[k];
            }
            if(cnt>1){                    //如果环中的个数超过1 
                if(flag) ans+=cnt-1;    //如果有0，则需要和0交换cnt-1 次 
                else ans+=cnt+1;        //如果没有0，需要先把0任意交换进环中，然后此时共cnt+1个数，需要交换cnt+1-1=cnt次
                                        //加上交换进去0的一次共cnt+1次 
            }
        }
    }
    cout<<ans;
    return 0;
}