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)$ 。