练84.2 光荣的梦想

解题思路

相邻交换最少次数等于逆序对数。使用归并排序，合并时右侧元素先于左侧剩余元素输出，就增加左侧未合并数量的逆序对。

正确性说明

每次交换相邻逆序数恰减少一个逆序对，因此逆序对数是必要次数下界；冒泡排序可每次减少一对直到有序，实现该下界。归并准确枚举所有跨左右段的逆序对。

易错点

相等不是逆序，左侧<=右侧时先取左侧。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n), tmp(n);
    for (auto &x : a)
        cin >> x;
    function<long long(int, int)> solve = [&](int l, int r) -> long long {
        if (r - l <= 1)
            return 0;
        int mid = (l + r) / 2;
        long long ans = solve(l, mid) + solve(mid, r);
        int i = l, j = mid, k = l;
        while (i < mid && j < r) {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else {
                tmp[k++] = a[j++];
                ans += mid - i;
            }
        }
        while (i < mid)
            tmp[k++] = a[i++];
        while (j < r)
            tmp[k++] = a[j++];
        for (int t = l; t < r; t++)
            a[t] = tmp[t];
        return ans;
    };
    cout << solve(0, n) << "\n";
    return 0;
}