H. Tom的世界冠军

单点时限: 0.5 sec

内存限制: 512 MB

在前辈们的不懈努力下 XX 协会终于拿了 n 块世界冠军奖牌 编号从 0 到 n−1，第 i 块奖牌本应该在第 i 个位置 ，但是由于没有经过好好的整理奖牌到处乱放，所以很乱，现在 Tom 要收拾奖牌 ，但是 Jerry 为了给 Tom 增加难度就设置了一个规则，就是每个奖牌只能与编号为0的奖牌交换位置，问最少需要交换多少次 ?

输入格式
第一行一个数字 n 表示奖牌的数量 (1≤n≤105)
第二行接下来 n 个数表示放乱的奖牌

输出格式
Tom 最少交换的次数

样例
input

7
1 3 2 4 6 5 0

output

4

题目大意

给你一个数 N 然后又 N 个数，每个数的大小都不超过 N ，每次交换只能用 0 去和其他数进行交换，问你最少交换多少次可以使这个数列为上升数列；这和谷歌的一道 和0交换次数的面试题一样

解题思路

为了使交换次数最少，所以我们应该使我们的每次操作尽可能的有价值。也就是每次操作尽可能的保证使一个数字变到属于它应该有的位置上；因此我们可以用一个数组记录每一个数字在哪一个位置，然后每次按照位置上的数进行交换；
比如说样例吧；0 在的位置下标是6；就先让0和6进行交换；然后数列就变成了
1 3 2 4 0 5 6 ；
但是此时数组下标为 0 的位置还不是0 继续进行交换，将0换到 （0的下标位置的数）所在的位置，
此时数列为 1 3 2 0 4 5 6；
此时还是不符合要求的，因此继续进行上述操作直到第一个数为 0 ；

代码

#include<bits/stdc++.h>
using namespace std;

int a[100009];
int main()
{
	int n,x;
	scanf("%d",&n);
	for(int i=0;i<n;i++) 
	{
		scanf("%d",&x);
		a[x]=i;
	}
	int sum=0;
	int mid;
	while(a[0]!=0)//因为第一个数肯定是零，所以看看现在这种情况满足不 
	{
		mid=a[0];//将 0 和 0在那个位置上的数的位置进行交换 
		a[0]=a[mid];//这样就使一个数字回到了他应该到的地方了； 
		a[mid]=mid;
		sum++;
	}
	for(int i=1;i<n;i++)
	{
		if(a[i]!=i)
		{
			a[0]=a[i];//先将这个数组和 0 进行交换； 
			a[i]=0;
			sum++;
			while(a[0]!=0)//继续执行第一个 while 的操作 
			{
				mid=a[0];
				a[0]=a[mid];
				a[mid]=mid;
				sum++;
			}
		}
	}
	printf("%d\n",sum);
	return 0;
}