题目描述

给定一个长度为$n$的整数数列，请你计算数列中的逆序对的数量。

样例

输入样例

6
2 3 4 5 6 1

输出样例

5

算法1

(暴力枚举) $O(n^2)$

C++ 代码

long long res = 0;
for(int i = 0; i < n; i ++)
{
    for(int j = i; j < n; j ++)
    {
        if(a[i] > a[j]) res ++;
    }
}

算法2

(归并排序) $O(nlog2n)$

用归并排序的思想：
1.分解 将待排序的数组从中间切割成两个子数组，直到待排序的数组长度为1
2.合并 将已经排好序的子数组逐步合并成一个更大的有序数组，直到合并成一个完整的有序数组。

要注意的是：每一次排序的时候左右两边的数组都是第一次见，不会存在重复的情况。
因为合并的两个子数组已经分别排好序了,(升序排列所以左边更小) 当左边数组a[i]出现大于右边数组a[j]的时候，那么i~mid这段数都会大于a[j] 。即 res += i - mid + 1;

C++ 代码

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

const int N = 1e5+10;
typedef long long ll;
int a[N],tmp[N];
int n;

ll merge(int l, int r)
{

    if(l >= r) return 0;
    int mid = l + r >> 1;
    ll res = 0;
    // 先排完左半边后排右半边 直到所有数组长度为1为止，然后开始合并
    res = merge(l, mid) + merge(mid + 1, r);
    int k = 0, i = l, j = mid + 1;

    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j])
        {
            tmp[k ++] = a[i ++];
        }
        else
        {
            res += mid - i + 1; // 当出现逆序对的时候，此时a[i] > a[j] 
                                //i~mid都大于a[j] 也就是说有mid-i+1个逆序对
            tmp[k ++] = a[j ++];
        }
    }
    while(i <= mid) tmp[k ++] = a[i ++];
    while(j <= r) tmp[k ++] = a[j ++];

    for(i = l,k = 0; i <= r; i ++, k ++) a[i] = tmp[k];
    return res;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];

    cout << merge(0,n-1) << endl;

    return 0;
}