[排序,贪心,置换环]洛谷P1327&&P8637,双倍经验

前置知识: 置换环,最小交换次数

https://blog.csdn.net/yunxiaoqinghe/article/details/113153795?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%9C%80%E5%B0%91%E4%BB%BB%E6%84%8F%E4%BA%A4%E6%8D%A2%E6%8E%92%E5%BA%8F%E8%AF%81%E6%98%8E%E7%94%A8%E7%BD%AE%E6%8D%A2&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-.pc_search_download_positive&spm=1018.2226.3001.4187

知道引理之后，我们可以很轻松的证明，我们在循环中执行的每一组交换操作，实际上就对应一个置换环。

代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#define For(i, j, n) for(int i = j ; i <= n ; ++i)
using namespace std;

const int N = 1e5 +5;

int n;
int a[N], b[N];
unordered_map<int, int> F;

int main()
{
    int ans = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++)
        F[b[i]] = i;
    for(int i = 1; i <= n; i++)
        while(a[i] != b[i])
        {
            swap(a[i], a[F[a[i]]]);
            ans++;
        }
    cout << ans << endl;
    return 0;
}

先通过排序，把每个数最后应该在的实际位置存下来，然后再根据这个结果进行交换和统计答案。

tips:

为什么不能在快速排序/归并排序的过程中顺便记录交换次数？

因为这些排序算法虽然是基于排序里面最优的，但是他们每次循环中也只能让当前的序列更靠近有序序列，他们所执行的步数>=ans，试想一下，如果能够在一遍排序的过程中直接统计出答案的话，那么这些排序的复杂度也就不会是NlogN了，就直接是N，这显然是存在矛盾的。