经典算法

分治算法-逆序对数量

输入一个 n 个数的序列 {a1, a2, a3, …., an} ，

求序列的逆序对数，即有多少个有序对 (i, j) 满足 i ＜ j 且 aᵢ > aⱼ ，其中 n ≤ 10⁶ 。

【输入描述】

输入两行。第一行为元素个数 n ；第二行是每个元素的值；

【输出描述】

输出一行。输出逆序对的数量。

【输入样例】

6
5 1 4 6 3 2
【输出样例】

9
【参考程序】

//小牛编程
#include <bits/stdc++.h>
using namespace std;

int arr[10001], ans = 0;

//合并
void merge(int arr[], int left, int mid, int right, int temp[]) {
    int i = left;
    int j = mid + 1;
    int t = 0;

    while (i <= mid && j <= right) {
        if (arr[i] < arr[j])
            temp[t++] = arr[i++];
        else {
            temp[t++] = arr[j++];
            // 统计个数
            ans += mid - i + 1;
        }
    }

    while (i <= mid)
        temp[t++] = arr[i++];

    while (j <= right)
        temp[t++] = arr[j++];

    t = 0;
    i = left;
    while (i <= right) {
        arr[i++] = temp[t++];
    }
}

void mergeSort(int arr[], int left, int right, int temp[]) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        //分
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid + 1, right, temp);

        //合
        merge(arr, left, mid, right, temp);
    }
}

int main() {
    int n;
    cin >> n;

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

    //调用归并排序函数
    int temp[n];
    mergeSort(arr, 0, n - 1, temp);

    cout << ans << endl;

    return 0;

}