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:
|
1 |
10 3 5 7 2 6 4 9 0 8 1 |
Sample Output:
|
1 |
9 |
与2015-2016秋冬学期PTA的Bonus 1一致。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<stdio.h> int found(int key,int *num,int n) { int i; for(i=0;i<n;i++) { if(num[i]==key) return i; } } void swap0(int *num,int n,int *count) { int temp,index; index=found(0,num,n); while(index!=0) { temp=found(index,num,n); num[index]=index; num[temp]=0; index=temp; (*count)++; } return ; } int swap0a(int *num,int *map,int *count) { int temp,index; index=map[0]; while(index!=0) { temp=map[index]; num[index]=index; num[temp]=0; map[0]=temp; map[index]=index; index=temp; (*count)++; } } int main() { int n,i,num[100000],map[100000],count=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",num+i); map[num[i]]=i; } swap0a(num,map,&count); for(i=0;i<n;i++) { if(num[i]!=i) { num[0]=num[i]; num[i]=0; map[num[0]]=0; map[0]=i; count++; swap0a(num,map,&count); } } printf("%d\n",count); } |