本文主要是介绍PAT 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------------------------------- 这是题目和解题的分割线-------------------------------
要想次数最少，必须0和0下标的数字交换。如果0交换到了0下标处，而此时还没交换完毕，则与一个不在本位的数字交换。
注意，这道题目容易超时。我最先的代码虽然表面没用二层循环，但时间复杂度也差不了多少。
//超时代码
#include<cstdio>
#include<algorithm>using namespace std;int main()
{int n,i,a[100005],pos,count = 0,num = 0;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]==0) pos = i;if(a[i]!=i&&a[i]) num++;}i = 0;while(num!=0){if(pos!=0){if(a[i]==pos){swap(a[i],a[pos]);pos = i;num--;count++;} }else{if(a[i]!=i){swap(a[i],a[pos]);pos = i;count++;}}i++; if(i==n) i = 0; //就是这两句话超时啦 }printf("%d",count);return 0;
} 
我的代码中这两句i++; if(i==n) i = 0导致循环次数太多，但为了找到结果为零的下标，不得已这样写。看书上的代码，换了个输入的办法，让读入的数作为数组下标，读入的数所在的位置作为数组内容，和常规相反，正好避免了找下标浪费时间的做法。
//AC代码
#include<cstdio>
#include<algorithm>using namespace std;int main()
{int n,a[100005],i,num,count = 0;scanf("%d",&n);for(i=0;i<n;i++){ int x;scanf("%d",&x);a[x] = i; //内容和下标反过来读取 if(x!=i&&x) num++; //除0以外不在本位的个数，因为最后一次交换会恢复两个数字的位置 }i = 1;//还存在不在本位的数字 while(num!=0){//0不在本位的时候(a[0]是0所在的下标)while(a[0]!=0){swap(a[0],a[a[0]]);num--;count++;}if(a[0]==0){//找到不在本位的数字进行交换 while(i<n){if(a[i]!=i){swap(a[i],a[0]);count++;break;}i++;}}}printf("%d",count);return 0;
}
这篇关于PAT 1067 Sort with Swap(0, i) [模拟]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
