P4639 元宇宙（提高）

解题思路

这道题的关键是看穿一个结论：让数列通过「交换相邻两个数字」变成升序，最少需要的交换次数，正好等于这个数列中逆序对的数量。

**第一步，读懂题意。**读入 n 和一个数列，输出把它变成升序所需要的最少相邻交换次数。

**第二步，理解什么是逆序对。**一对下标 i < j，但数字 numbers[i] > numbers[j]，也就是「前面的数比后面的数大」，这样的两个数就构成一个逆序对。比如数列 2 1 4 3 中，(2,1) 和 (4,3) 都是逆序对，共 2 对，而样例答案正好是 2。

**第三步，为什么最少次数等于逆序对数量。**每一次交换相邻的两个数，最多只能消除一个逆序对：如果这两个数是「前面大后面小」，交换后它们就变对了，逆序对少一个；如果它们本来就是对的，交换反而会产生逆序对。所以想最终排好序（逆序对为 0），至少要交换逆序对数量那么多次；而每次都去交换相邻的逆序对，就刚好能做到。所以最少次数就是逆序对总数。

**第四步，用归并排序高效统计。**n 最大 10000，用两重循环挨个比较要 O(n²) 次，可能比较慢。改用归并排序，在排序的同时顺便统计逆序对，复杂度只有 O(n log n)。

**第五步，理解归并时怎么数。**归并排序把数列不断对半拆成小段，每段排好序后再合并。合并左右两个有序区间时，如果右边的数比左边当前的数小，那么这个右边的数和左边剩余的所有数都构成逆序对，答案一次性加上「左边剩余个数」即可，这样不重不漏。

**第六步，注意答案用 long long。**n 最大 10000 时，逆序对最多接近 5000 万，可能超过 int 范围，所以答案变量必须用 long long 保存。

参考代码

// 用归并排序统计逆序对，逆序对数量就是相邻交换的最少次数。
#include <iostream>
using namespace std;

// 合并两个有序区间，并统计左边较大的数字造成的逆序对。
void msort(int numbers[], int temp[], int left, int right, long long &count) {
    if (left >= right) return; // 一个数字本身已经有序。
    int mid = (left + right) / 2; // 把区间分成左右两半。
    msort(numbers, temp, left, mid, count); // 先处理左半部分。
    msort(numbers, temp, mid + 1, right, count); // 再处理右半部分。
    int i = left; // 左半部分当前下标。
    int j = mid + 1; // 右半部分当前下标。
    int k = left; // 临时数组当前下标。
    while (i <= mid && j <= right) { // 两边都还有数字时进行比较。
        if (numbers[i] <= numbers[j]) { // 左边数字较小时直接放入临时数组。
            temp[k] = numbers[i]; // 保存左边数字。
            i++; // 左边下标向后移动。
        } else { // 右边数字更小时形成逆序对。
            temp[k] = numbers[j]; // 保存右边数字。
            count += mid - i + 1; // 左边剩余数字都比它大。
            j++; // 右边下标向后移动。
        }
        k++; // 临时数组下标向后移动。
    }
    while (i <= mid) { // 把左边剩余数字放入临时数组。
        temp[k] = numbers[i]; // 保存左边剩余数字。
        i++; // 左边下标向后移动。
        k++; // 临时数组下标向后移动。
    }
    while (j <= right) { // 把右边剩余数字放入临时数组。
        temp[k] = numbers[j]; // 保存右边剩余数字。
        j++; // 右边下标向后移动。
        k++; // 临时数组下标向后移动。
    }
    for (i = left; i <= right; i++) { // 把合并结果放回原数组。
        numbers[i] = temp[i]; // 更新当前数字。
    }
}

int main() {
    int n; // 数列长度。
    int numbers[10005]; // 保存原数列。
    int temp[10005]; // 归并时使用的临时数组。
    int i; // 输入循环变量。
    cin >> n; // 读入数列长度。
    for (i = 0; i < n; i++) { // 读入数列中的每个数字。
        cin >> numbers[i]; // 保存一个数字。
    }
    long long count = 0; // 逆序对数量，也就是最少交换次数。
    msort(numbers, temp, 0, n - 1, count); // 统计整个数列的逆序对。
    cout << count << '\n'; // 输出最少交换次数。
    return 0; // 程序正常结束。
}

复杂度分析

时间上，归并排序每次把区间分成两半，递归深度是 log2(n)，每层合并时把所有元素扫描一遍，所以时间复杂度是 O(n log n)。n 最大 10000，log2(10000) 约等于 14，总共大约十几万次操作，速度很快。空间上，需要一个与原数组同样大小的临时数组，空间复杂度是 O(n)。相比 O(n²) 的两重循环暴力统计，这个算法效率高得多。