PAT 1067 Sort with Swap[难]

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

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

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

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

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

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

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

学习了！