归并排序

归并排序的时间复杂度是 \(O(nlog(n))\) 时间稳定。

归并排序模板

int a[N], b[N], n;

void merge(int l, int mid, int r)
{
    int i = l, j = mid + 1, t = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] > a[j]) b[t ++] = a[j ++];
        else b[t ++] = a[i ++];
    }
    while (i <= mid) b[t ++] = a[i ++];
    while (j <= r) b[t ++] = a[j ++];
    for (i = 0; i < t; i ++) a[l + i] = b[i];
}

void msort(int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) / 2;
    msort(l, mid);
    msort(mid + 1, r);
    merge(l, mid, r);
}

归并排序求逆序对模板

归并排序求逆序对

LL a[N], b[N], cnt; // cnt 代表的是逆序对的数量

// 归并排序统计逆序对
void merge(LL l, LL mid, LL r)
{
    LL i = l, j = mid + 1, t = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] > a[j])
        {
            b[t ++] = a[j ++];
            cnt += mid - i + 1; 
            // 如果左区间第 i 个元素大于右区间第 j 个元素
            // 按照归并排序的特点，左区间和右区间都已经是单调递增了的
            // 那么逆序对的数量要增加 mid - i + 1 个.
        }
        else b[t ++] = a[i ++];
    }
    while (i <= mid) b[t ++] = a[i ++];
    while (j <= r) b[t ++] = a[j ++];
    for (i = 0; i < t; i ++) a[l + i] = b[i];
}

void msort(LL l, LL r)
{
    if (l >= r) return;
    LL mid = (l + r) / 2;
    msort(l, mid); msort(mid + 1, r);
    merge(l, mid, r);
}

序列中逆序对的数量，例如对于序列 \(1, 2, 6, 3, 4, 5\) 逆序对有 \(<6, 3>、<6, 4>、<6, 5>\) 总共 \(3\) 个。

减少逆序对

bobo 有一个长度为 \(n\) 的非负整数序列 \(a_1, a _ 2, a_3, \cdots , a _ n\)，他至多允许你交换 \(k\) 次相邻数。

逆序对的定义：对于 \(1 \leq l \leq r \leq n\) ，若 \(a_i > a_j\) 就为一对逆序对，用语言描述就是大的排在小的左边，就为一对逆序对。

请求出交换之后的逆序对最少数量。

输入格式

对于每个测试样例，第一行有两个整数 \(n，k\)，第二行有 \(n\) 个整数。

输出格式

对于每个测试样例，输出一个整数并换行。

1
2

归并排序求逆序对思路

若 \(k = 0\)，那么答案就是逆序对的数量；

我们如何才能减少逆序对的数量？

对于例子 \(1,2,3,6,4,5\) 逆序对有 \(2\) 个；

对不是逆序对的相邻数交换一次，例如交换 \(1、2\)：\(2,1,3,6,4,5\) ，逆序对变为 \(3\) 个，反而还变多了；

若交换相邻数且符合逆序对的，例如交换 \(6、4\)：\(1,2,3,4,6,5\) 逆序对数减少为 \(1\).

我们是否有结论：只要交换 \(k\) 次连续的逆序对是否就可以将逆序对数量从原来的 \(x\) 减低到 \(x - k\) ?

若有连续的逆序对，并使其交换一次是一定可以使得总逆序对的数量只降低一次

那是不是一定存在连续的逆序对呢？

反证法： 假设原序列存在逆序对，但是不存在连续的逆序对，那么该序列任意一对连续的数都是单调递增的，这会导致总序列单调递增，就会不存在逆序对，与原假设矛盾，所以一定存在连续的逆序对。

归并排序求逆序对

#include <iostream>

using namespace std;

const int N = 1e7 + 10;

typedef long long LL;

LL a[N], b[N], cnt;

// 归并排序统计逆序对
void merge(LL l, LL mid, LL r)
{
    LL i = l, j = mid + 1, t = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] > a[j])
        {
            b[t ++] = a[j ++];
            cnt += mid - i + 1; 
            // 如果左区间第 i 个元素大于右区间第 j 个元素
            // 按照归并排序的特点，左区间和右区间都已经是单调递增了的
            // 那么逆序对的数量要增加 mid - i + 1 个.
        }
        else b[t ++] = a[i ++];
    }
    while (i <= mid) b[t ++] = a[i ++];
    while (j <= r) b[t ++] = a[j ++];
    for (i = 0; i < t; i ++) a[l + i] = b[i];
}

void msort(LL l, LL r)
{
    if (l >= r) return;
    LL mid = (l + r) / 2;
    msort(l, mid); msort(mid + 1, r);
    merge(l, mid, r);
}

void solve()
{
    LL n, k;
    while (cin >> n >> k)
    {
        cnt = 0;
        for (LL i = 1; i <= n; i ++) cin >> a[i];
        msort(1, n); 
        if (cnt <= k) cout << 0 << endl;
        else cout << cnt - k << endl;
    }
}

int main(void)
{
    solve(); return 0;
}