PAT (Advanced Level) 1067. Sort with Swap(0,*) (25)

只对没有归位的数进行交换。

分两种情况：

如果0在最前面，那么随便拿一个没有归位的数和0交换位置。

如果0不在最前面，那么必然可以归位一个数字，将那个数字归位。

这样模拟一下即可。

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<map>

#include<stack>

#include<queue>

#include<string>

#include<algorithm>

using namespace std;

int n;

int a[+];

queue<int>Q;

int pos[+];

int main()

{

    scanf("%d",&n);

    for(int i=;i<n;i++) scanf("%d",&a[i]);

    for(int i=;i<n;i++) pos[a[i]]=i;

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

    {

        if(a[i]==) continue;

        if(a[i]!=i) Q.push(a[i]);

    }

    int ans=;

    while()

    {

        if(a[]==)

        {

            while(!Q.empty())

            {

                int head=Q.front(); Q.pop();

                if(a[head]==head) continue;

                else

                {

                    ans++;

                    int pos1=pos[];

                    int pos2=pos[head];

                    swap(a[pos1],a[pos2]);

                    swap(pos[head],pos[]);

                    break;

                }

            }

            if(Q.empty()) break;

        }

        else

        {

            ans++;

            int pos1=pos[];

            int pos2=pos[pos[]];

            int num1=;

            int num2=pos[];

            swap(a[pos1],a[pos2]);

            swap(pos[num1],pos[num2]);

        }

    }

    printf("%d\n",ans);

    return ;

}