题意：依据题目要求交换相邻的两个元素k次，使得最后剩下的逆序对数最少

思路：假设逆序数大于0，存在0 <= i < n使得交换Ａi，Ａi+1后逆序数降低1，所求答案就为max(inversion - k, 0);

利用归并排序计算逆序对数。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN = 1000005;

int arr[MAXN], b[MAXN];

int n, k;

long long cnt;

void merge_sort(int * a, int x, int y, int *b) {

    if (y - x > 1) {

        int m = x + (y - x) / 2;

        int p = x, q = m, i = x;

        merge_sort(a, x, m, b);

        merge_sort(a, m, y, b);

        while (p < m || q < y) {

            if (q >= y || (p < m && a[p] <= a[q]))

                b[i++] = a[p++];

            else {

                b[i++] = a[q++];

                cnt += m - p;

            }

        }

        for (i = x; i < y; i++)

            a[i] = b[i];

    }

}

int main() {

    while (scanf("%d%d", &n, &k) != EOF) {

        for (int i = 0; i < n; i++)

            scanf("%d", &arr[i]);

        cnt = 0;

        merge_sort(arr, 0, n, b);

        if (cnt - k > 0)

            cnt -= k;

        else

            cnt = 0;

        cout << cnt << endl;

    }

    return 0;

}