PAT甲级真题 1067 Sort with Swap(0, i) (25分) C++实现（注意测试点1、2超时问题）

题目

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 (<=105) 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

思路

初始序列：

3 5 7 2 6 4 9 0 8 1

对应的变换为：

3 5 0 2 6 4 9 7 8 1
3 5 2 0 6 4 9 7 8 1
0 5 2 3 6 4 9 7 8 1
5 0 2 3 6 4 9 7 8 1
5 1 2 3 6 4 9 7 8 0
5 1 2 3 6 4 0 7 8 9
5 1 2 3 0 4 6 7 8 9
5 1 2 3 4 0 6 7 8 9
0 1 2 3 4 5 6 7 8 9

为了快速找到元素位置，用pos数组存储每个值的位置。问题即转化为：如何修改pos数组的值，使得所有的pos[i] = i。

变换的方法是：

1. 当pos[0] = i，且 i != 0 时，持续交换pos[0] 和 pos[i]；
2. 当pos[0] = 0，检查是否仍存在错位。设置checkPos表示已检查无错位的位置，初始化为1，每次检查都从checkPos向后检查。若有错位i（如上例中第3步变换后），则交换pos[0] 和 pos[i]然后重新执行1中的操作。直到pos[0] =0 且数列中不存在错位为止。

注意，如果不记录已检查位置，每次都从头检查的话，测试点1、2会超时。

代码

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> pos(n);
    for (int i=0; i<n; i++){
        int temp;
        scanf("%d", &temp);
        pos[temp] = i;
    }
    int count = 0;
    int checkPos = 1;
    bool sorted = false;
    while (!sorted){
        //swap(0, i)
        while (pos[0] != 0){
            int i = pos[0];
            pos[0] = pos[i];
            pos[i] = i;
            count++;
        }
        //检查是否仍存在错位
        while (checkPos<n && pos[checkPos]==checkPos){
            checkPos++;
        }
        if (checkPos==n){
            sorted = true;
        }
        else{  
            //swap(0, i)
            pos[0] = pos[checkPos];
            pos[checkPos] = 0;
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}