PAT甲题题解-1067. Sort with Swap(0,*) (25)-贪心算法

贪心算法

次数最少的方法，即：
1.每次都将0与应该放置在0位置的数字交换即可。
2.如果0处在自己位置上，那么随便与一个不处在自己位置上的数交换，重复上一步即可。
拿样例举例：
   0 1 2 3 4 5 6 7 8 9
0:3 5 7 2 6 4 9 0 8 1

1:3 5 0 2 6 4 9 7 8 1
2:3 5 2 0 6 4 9 7 8 1
3:0 5 2 3 6 4 9 7 8 1 (如果0处在自己位置上，那么找一个不在自己位置上的数val与之交换)
4:5 0 2 3 6 4 9 7 8 1
5:5 1 2 3 6 4 9 7 8 0
6:5 1 2 3 6 4 0 7 8 9
7:5 1 2 3 0 4 6 7 8 9
8:5 1 2 3 4 0 6 7 8 9
9:0 1 2 3 4 5 6 7 8 9

在例子第3步交换中，如果每次都线性查找，时间复杂度就会很高，会有2组样例超时。
这里用set优化了下速度。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <vector>

#include <set>

using namespace std;

const int maxn=+;

int a[maxn];

int pos[maxn];

int cnt;

set<int> leftnum; //存储了还没有被放到正确位置上的数字(0除外)

int main()

{

    int n;

    scanf("%d",&n);

    cnt=n; //还未排好序的个数

    for(int i=;i<n;i++){

        scanf("%d",&a[i]);

        pos[a[i]]=i;

        if(i==a[i])

            cnt--;

        else if(a[i]!=)

            leftnum.insert(a[i]);

    }

    int p0=pos[]; //0目前所在的位置

    int p;

    int ans=;

    while(cnt){

        //将0和应处在0位置的数(p0)交换位置

        a[p0]=p0;

        leftnum.erase(p0);

        p0=pos[p0];

        a[p0]=;

        ans++;

        cnt--;

        if(p0==)

            cnt--;

        //如果0在自己位置上，但还没有排好序

        if(p0== && cnt){

            //这里用set来优化寻找还没有处在自己位置上的数字，将0与之交换

            int val=*leftnum.begin();

            int tmp=pos[val];

            pos[val]=p0;

            a[p0]=val;

            p0=tmp;

            a[p0]=;

            ans++;

            cnt++;

        }

    }

    printf("%d",ans);

    return ;

}