PAT_A1067 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 <bits/stdc++.h>
using namespace std;
const int N = 100000+5;
int e[N], c, n, r, p[N]; 

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", e+i);
		p[e[i]] = i;
		if(e[i] != 0 && e[i] == i) c++;
	}
	int ne = 1;
	while(c != n-1)
		if(p[0] != 0){
			swap(p[0], p[p[0]]);
			c++;
			r++;
		}else
			while(ne < n){
				if(p[ne] != ne){
					swap(p[0], p[ne]);
					r++;
					break;
				}
				ne++;
			}
	printf("%d", r);
	return 0;
}

总结
1、 #贪心 使用p数组存放各元素当前所处位置，e数组在这里无用。如果0的位置为i（i!=0），则swap(p[0], p[i])；如果i=0，让没有归位的元素的位置与之互换。
2、在寻找没有归位的元素时，如果每次从头开始寻找会超时 $o(n^2)$ ，有测试点无法通过。这里定义了ne，保存目前序列中本位上的最小元素（初始为1），每次从ne递增寻找 $o(n)$ 。