PAT (Advanced Level) Practice 1067 Sort with Swap(0, i) (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(\le 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

思路

• 每一次把0和0所在位置的数交换,如果0回到了自己的位置, 那么寻找没有回到位置的元素和它交换
• num2pos[]数组记录了每个数字的位置
• 每一次寻找不用从头开始,因为前面已经确认过在自己的位置上, 之后除了0会变动,其他的数字不会再交换离开自己的位置了, 所以从上一次确认过的位置开始继续确认(即cur)

AC code

#include<iostream>
using namespace std;int num2pos[100005];
int main(){
    int n,x;scanf("%d",&n);for(int i=0;i<n;i++){
    scanf("%d",&x);num2pos[x]=i;}int ans=0,cur=0;while(cur<n){
    while(num2pos[0]){
    swap(num2pos[0],num2pos[num2pos[0]]);ans++;}if(num2pos[cur]==cur) cur++;else{
    swap(num2pos[0],num2pos[cur]);ans++;}}printf("%d",ans);
}