1067 Sort with Swap(0, i)

题目

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:

分析

本题的主要思路就是贪心算法，即每次交换的时候，都尽可能的使一个元素正确的归位。最直接的想法就是，用一个数组记录原始数据，然后用一个hash map记录元素所在位置。每次都从0元素开始，当0元素不在正确的位置时，将其和0所在的位置应该放置的元素进行交换，这样就完成了一个元素的归位。当出现0元素已经归位但是整体序列还不是有序的情况时，我们选择序列中的一个还处于无序状态的元素，将其和0元素交换位置，然后再重复上述过程。最初的想法就是，没交换一次，就对整体的序列进行一次扫描判断是否全部有序，但是有两个样例无法通过。后来对这个判断是否有序的方法进行了改进，在最开始录入原始数据的时候，记录一下一共有多少个元素是无序的，然后循环的退出条件就变成了判断当前归位的元素数是否达到要求即可。这样优化了以后还是无法通过样例。。最后参考了一下题解，发现问题出在了寻找一个处于无序状态的元素这一步。题解给出的方法是再维护一个变量，记录当前未复位的位置最小的一个元素的位置。这样整体程序就显得比较复杂了。然后我又发现了一种更加巧妙的解法，整体思路是：使用a[t]=i记录t在i位置，依次遍历每个位置，如果当前位置不正确，则让0号来执行下列操作使其回到正确位置：如果0号现在不在有序位置（0位），那就让0号和此数字交换位置，直到0号回到有序位置。然后再次检查此位置是否是正确的，如果不是，就让0号和其交换位置，如果是，那就直接跳过。这里这一步就是此算法中最巧妙的一步，用这种方式完成了“维护一个未归位的元素的最小位置”这一操作。到达最后一个位置的时候，如果0号和最后一个数字都有序就正确，否则交换位置即可。

代码

#include<iostream>

using namespace std;

int main(){
    int n, t, cnt = 0, a[10010];
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> t;
        a[t] = i;
    }
    for(int i = 1; i<n; i++){
        if(a[i] != i){
            while(a[0] != 0){
                swap(a[0], a[a[0]]);
                cnt += 1;
            }
            if(i != a[i]){ // 当0归位但是a[i]还无序时 交换
                swap(a[0], a[i]);
                cnt += 1;
            }
        }
    }
    cout << cnt;
    return 0;
}