Inversion

1. 题目核心解析

什么是逆序对与交换的关系？

题目中提到：“最多可以进行 $k$ 次相邻数字的交换操作”。

这是一个非常重要的性质：交换两个相邻的元素，只会改变这对元素之间的逆序关系，而不会影响它们与其他元素的逆序关系。

如果 $a_i > a_{i+1}$ （这是一个逆序对），交换它们后，变成 $a_{i+1} < a_i$ ，逆序对数量 减 1。
如果 $a_i < a_{i+1}$ （不是逆序对），交换它们后，变成 $a_{i+1} > a_i$ ，逆序对数量 加 1。

我们的目标

我们要让逆序对数量最小。显然，我们只应该执行那些能让逆序对数量减少的操作（即交换那些 $a_i > a_{i+1}$ 的相邻对）。

这其实就是冒泡排序 (Bubble Sort) 的原理。冒泡排序中每一次有效的交换，都消除了一个逆序对。

结论

要把一个序列变成完全有序（逆序对数量为 0），所需要的最少相邻交换次数，严格等于该序列的初始逆序对总数（设为 $cnt$ ）。

如果我们有足够的次数 ( $k \ge cnt$ )，我们可以把逆序对全部消除，结果为 0。
如果次数不够 ( $k < cnt$ )，我们每用一次机会，就能消除一个逆序对。用完 $k$ 次后，剩下的逆序对数量就是 $cnt - k$ 。

所以，最终答案就是：

\max(0LL, \text{总逆序对数量} - k)

2. 算法选择

问题的核心变成了：如何快速求出一个序列的逆序对总数？

暴力法：两层循环枚举 $(i, j)$ 。复杂度 $O(N^2)$ 。
- 题目中 $N \le 10^5$ ，暴力法计算量约为 $10^{10}$ ，肯定会 超时 (TLE)。
归并排序 (Merge Sort)：在归并的过程中计算逆序对。复杂度 $O(N \log N)$ 。
- 推荐使用。这是最标准的解法。
树状数组 (Fenwick Tree) / 线段树：配合离散化使用。复杂度 $O(N \log N)$ 。
- 因为 $a_i$ 很大 ( $10^9$ )，必须先离散化才能用树状数组。相比归并排序稍微麻烦一点点。

3. 归并排序求逆序对的原理

在归并排序的合并 (merge) 阶段，我们有两个已经排好序的子数组，比如：

左边：[2, 5, 8] (指针 i)

右边：[1, 3, 6] (指针 j)

当我们在合并时：

比较 2 和 1。因为 2 > 1，说明 1 应该放在 2 前面。
关键点：既然 2 比 1 大，那么左边数组里 2 后面的所有数（5, 8）肯定也都比 1 大（因为左边是有序的）。
所以，此时构成的逆序对数量就是 左边数组剩余元素的个数。
- 即 mid - i + 1。

4. AC 代码 (C++ 归并排序版)

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;
int a[maxn];
int temp[maxn]; // 归并排序需要的辅助数组
ll total_inversions = 0; // 逆序对总数，注意要用 long long

// 归并排序的同时计算逆序对
void merge_sort(int l, int r) {
    if (l >= r) return;

    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    // 开始合并
    int i = l, j = mid + 1, k = l;
    
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            // a[i] > a[j]，构成了逆序对
            // 左边 a[i] 以及它后面的所有数 (直到 mid) 都比 a[j] 大
            temp[k++] = a[j++];
            total_inversions += (long long)(mid - i + 1);
        }
    }

    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];

    // 拷贝回原数组
    for (int p = l; p <= r; ++p) {
        a[p] = temp[p];
    }
}

void solve() {
    int n;
    ll k;
    // 处理多组输入
    while (cin >> n >> k) {
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }

        total_inversions = 0; // 每次都要清零
        merge_sort(1, n);

        // 答案是 总逆序对 - k，但不能小于 0
        if (k >= total_inversions) {
            cout << 0 << "\n";
        } else {
            cout << (total_inversions - k) << "\n";
        }
    }
}

int main() {
    // 加速 I/O
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    solve();
    
    return 0;
}

5. 易错点提示

数据类型：逆序对的数量最多可以是 $N \times (N-1) / 2$ 。当 $N=10^5$ 时，约为 $5 \times 10^9$ ，超过了 int 的范围（int 最大约 $2 \times 10^9$ ）。必须使用 long long 存储逆序对数量。
多组数据：题目说了“输入包含多组测试数据”，所以要用 while(cin >> n >> k) 包裹。每次新的一组数据开始前，要把计数器清零。
负数处理：计算 ans - k 时，如果 k 很大，结果可能是负数。题目求的是数量，不能输出负数，要和 0 取最大值。

这道题其实是归并排序模板题披了一层“交换”的皮。只要看穿了“交换次数=逆序对减少量”这个本质，问题就迎刃而解了。

目录