1067 Sort with Swap(0,*) (25)（25 分）

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 (<=10^5^) 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

 题目大意：现在只有swap(0,*)这个操作来实现排序，也就是将0和*进行交换排序，找出最少的操作次数。

 //我不太会，我只能想到是的有点像快排，当0所在的下标<n/2时，就从右边开始遍历选最小的数换，反之取最大的数换，但是这样明显不是次数最少的，所以我不会。

代码来自：https://www.liuchuo.net/archives/2301

#include 
     
      #include 
      
       using namespace std;int main() {    int n, num, cnt = 0, ans = 0, index = 1;    scanf("%d", &n);    vector
       
         v(n);    for(int i = 0; i < n; i++) {        scanf("%d", &num);        v[num] = i;//保存当前数所在的位置。        if(num != i && num != 0) cnt++;    }    while(cnt > 0) {        if(v[0] == 0) {            while(index < n) {                if(v[index] != index) {                    swap(v[index], v[0]);//直接用swap函数是多么简单。                    ans++;                    break;                }                index++;            }        }        while(v[0] != 0) {            swap(v[v[0]], v[0]);            ans++;            cnt--;        }    }    printf("%d", ans);    return 0;}
       
      
     

 

//当时看解题思路，似乎懂了一些，但是自己写还是不对，真是绝望，好笨。

1.使用向量记录的是数字所在的位置，而不是当前位置放的是谁，这样就简单了，因为每次都要找数字所在的下标位置。

2.使用index来记录，因为每次循环到index之前的都已经存储好了，index是指数1，数2，数3是否存到了正确的位置。

3.当0不在0的位置上时，一直循环交换即可。

#include 
     
      #include 
      
       #include 
       
        using namespace std;int a[10000];int main() {    int n,index=0;//index指向0所在的位置。    cin>>n;    int ct=0;//标记有多少不在原位的，在原位的肯定就不去挪了。    for(int i=0;i
        
         >a[i];        if(a[i]==0)            index=i;//标记住i的下标。        if(a[i]!=i&&i!=0           )            ct++;    }    int t,no=0;    while(ct!=0){        if(index!=0){            for(int i=0;i
        
       
      
     

 

//终于理解了为什么自己错了，因为当0回到0位置时，应该选取1，2，3依此数字最小的而不是位置上不等于当前位置的！

学习了！