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,1,...,N-1\}$ 的一个序列，要求通过两两交换的方式将其变为递增序列，但是每一次交换必须用 0 与其它数进行交换。求最小交换次序。

思路

贪心算法：要求一个问题的最优解，先求局部最优解，即就是中间每一步都要是最优解

本题中，如果当前 0 处于 i 号位，则找到数字 i 当前所处的位置，然后把 0 与 i 进行交换，此时数字 i 就位于它的最终位置上，取得了最优解。

技巧：

这个题目给的数据范围比较大，我们可以建立字典，数字 `i` 对应的下标记录下来，避免因寻找数字 `i` 而超时，同时每一次交换（一个特殊情况除外）都会将一个数归位，所以将这个字典 `key` 删去即可，当字典中只剩下 `key=0` 时，所有数据都已归位。

这里需要考虑一种情况，0 在交换的过程中可能归位，这是需要在 map 中任取一个数与之交换。具体见代码。

代码

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

int main(){
    int n;
    vector<int> a(100000);
    map<int,int> mp;
    scanf("%d", &n);
    for(int i=0, t; i<n; i++){
        scanf("%d", &t);
        a[i] = t;
        if(t != i)    // map只存储未归位的数据
            mp[t] = i;
    }
    int ans = 0;
    while(mp.size() > 1){    // map中只有0时结束
        if(a[0] != 0){
            int i = mp[0], j = mp[i];
            a[i] = a[j], a[j] = 0;
            mp.erase(a[i]);    // 数据归位，从字典中删除
            mp[0] = j;         // 修改0的位置
        }
        else{
            map<int,int>::iterator it = ++mp.begin(); // map.begin()为0，故需要加一
            int i = it->second, t = it->first;
            a[0] = t, a[i] = 0, mp[t] = 0, mp[0] = i;
        }
        ans++;
//        for(int i=0; i<n; i++)
//            printf("%d ", a[i]);
//        printf("\n");
    }
    printf("%d\n", ans);
    return 0;
}