题目大意
给出一个n个数的序列，数字为0~n-1的乱序，每次只能用数字0和另一个数交换。经过若干次能使序列变成有序的，问最少需要几次交换。
思路
贪心策略。 （1）每次让0占的位置上本来应该占的数字与0交换，交换结束后该数归位。 （2）但有可能数字0在自己的位置上（即第0位），但仍有其他数字没有归位。则此时将0与其交换，让它暂时占据0位，重复步骤（1）。 优化： 在（2）中，如果每次都循环去找没有归位的数字，若那个数字在很后面，则要判断很多次，测试点1、2会超时。因此最外层循环是i从数字0到数字n-1，每一次循环结束后，数字i的状态可能有两种，一种是在0不断“让位”中归位（即它与0处在同一个错位圈中）；另一种是0不断“让位”也不能导致它归位，则强制让它暂时占据0位，在下一次循环的时候，数字0要想回到0位，必须通过与它交换才可以（则在代码中的while循环内实现），而0与它交换的条件只能是因为0占据了它本来的位置，则它必然能在下一次循环中归位。
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#define MAX 100000
int main() {
int i, temp, times = 0, n, locate[MAX];
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &temp);
locate[temp] = i;
}
for (i = 1; i < n; i++) {
while (locate[0] != 0) {
temp = locate[locate[0]];
locate[locate[0]] = locate[0];
locate[0] = temp;
times++;
}
//如果每次判断0归位后，再寻找没归位的数字，就会多余循环判断，引起超时。
if (locate[i] != i) {//此时代表数字0已归位，但是数字i仍然不在自己的位置上
//则需要交换0和i，也即数字0的位置和数字i的位置对调
temp = locate[i];
locate[i] = locate[0];
locate[0] = temp;
times++;
}
}
printf("%d", times);
return 0;
}
