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:

题目大意：现在只有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依此数字最小的而不是位置上不等于当前位置的！

学习了！

巴特西

PAT 1067 Sort with Swap[难]

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

最新文章

热门文章