1067 Sort with Swap(0, i)

Given any permutation of the numbers {0, 1, 2,..., N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:

Each input file contains one test case, which gives a positive N (≤105) followed by a permutation sequence of {0, 1, ..., N−1}. All the numbers in a line are separated by a space.

Output Specification:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:

10
3 5 7 2 6 4 9 0 8 1

Sample Output:

9

代码： 

#include 
#include 
using namespace std;
int n, a[100010], b[100010], ans, t, x, y, ind[100010], cnt, fIndex;
bool flag;
 
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		b[i] = a[i];
		ind[a[i]] = i;
	}
	sort(b, b + n);
	for (int i = 1; i < n; i++) {
		if (a[i] != b[i]) {
			cnt++;//记录位置不对的个数
		}
	}
	while (true) {
		while (a[0] != 0) {
			t = ind[0]; //t是0的下标
			x = b[ind[0]]; //x是应该在此时0的位置的数
			y = ind[x]; //y是  应该在此时0的位置的数  的下标
			a[y] = 0;
			a[t] = x;
			ind[0] = y;
			ind[x] = t;
			ans++;
			cnt--;
		}
		flag = 1;
		if (cnt == 0) {//顺序不对的个数归零时排序已完成
			printf("%d", ans);
			break;
		}
		//此时a[0]=0，但是不一定完成移动，选择第一个顺序不对的数与0交换
		for (int i = fIndex; i < n; i++) {//fIndex记录第一个顺序不对的数的下标，及时更新
			if (a[i] != b[i]) {
				ind[0] = i;
				ind[a[i]] = 0;
				a[0] = a[i];
				a[i] = 0;
				ans++;
				flag = 0;
				fIndex = i;
				break;
			}
		}
		if (flag) {
			printf("%d", ans);
			break;
		}
	}
	return 0;
}

 测试点12超时 参考博客：[PAT]1067 Sort with Swap(0, i) (25 分)(运行超时解决办法)_刘好念的博客-CSDN博客