问题描述

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?
Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers. 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}

Input Specification:
Each input file contains one test case, which gives a positive N (≤10⁵) 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.

解决方法

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int arr[maxn];
//定义一个map用作 值-位置 的映射
map<int,int> list;
int main(void)
{
    int m, res = 0;
    scanf("%d", &m);
    int current = 0,temp = 0;
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &temp);
        //只将会发生位置交换的实体(entry)放进map中
        if(temp != i)
            list[temp] = i;
    }


    while (true) 
    {
        //交换直到0在位置0上
        while (list[0] != 0)
        {
            int temp = list[0];
            //交换后将位置和值相同的实体移除 保证map中只有需要进行交换的实体
            swap(list[0], list[list[0]]);
            list.erase(list.find(list[temp]));
            res++;
        }
        //如果map中只剩下0-0说明已经排序好了跳出即可
        if (list.size() == 1) 
        {
            break;
        }
        else  //否则找到下一个未排序好的实体进行位置的交换
        {
            swap(list[0], (++list.begin())->second);
            res++;
        }
    }

    //输出结果
    printf("%d", res);
    return 0;
}

基本策略

• 循环选择0和0当前位置对应的值做交换,如果0因为交换而回到0位置,判断是否还有没排好序的值。
  • 如果没有没排好序的值,说明已经排好顺序了结束并返回结果
  • 如果还有没排好序的值，就将0和其交换之后重复一开始的循环交换

遇到的问题

• 一开始使用平常的循环去写，很顺利但是在第二三个测试用例(数据量很大)出现超时的情况，因为循环中一直在检测不可能变换位置的值导致超时，因此选择map来对位置和值做个映射并且可以动态的删除其中排好序的值才可以完美通过

结果展示

patA1067.png