PAT A1067 Sort with Swap(0, i) (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>

using namespace std;
/* 对n个非负整数进行排序(从0~n-1)，但只允许swap(0,*)操作；swap(0,y)表示将0和y的位置进行交换， 问你将这n个数进行升序排序，最少需要进行几次swap(0,*)操作 思路： 如果数字0在i号位，则找到数字i的当前位置，将然后把0和i进行交换； 如果数字0是在0号位，那么需要随便选择一个还没有回到本位的数字，将0与该数字进行交换 注意点： 1、每次只能与0进行交换，一旦某个数字回到本位后，则不对该数字进行后续操作 2、在随便选择一个还没回到本位的数字时，可以定义一个变量k，用来保存当前不在本位上的最小数（初始为1） 3、数组pos记录每个数字的位置 */
const int N=1e5+10; 
int pos[N],n,res=0;
int main(){
	scanf("%d",&n);
	int last=n-1,num;//last表示除0以外不在本位上的数的个数
	for(int i=0;i<n;i++){
		scanf("%d",&num);
		pos[num]=i;//数字num在i号位
		if(num!=0&&num==i) last--;//如果除零以外有在本位上的数 
	} 
	int k=1;//k表示当前不在本位上的最小数
	while(last>0){
		if(pos[0]==0){//如果0在本位 
			while(k<n){//找一个不在本位上的数进行交换 
				if(pos[k]!=k){
					swap(pos[0],pos[k]);
					res++;
					break;
				}
				k++;
			}
		}
		while(pos[0]!=0){//0不在本位 
			swap(pos[0],pos[pos[0]]);
			res++;
			last--; 
		}
	} 
	printf("%d\n",res);
	return 0;
}