AcWing 788. 逆序对的数量

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

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1 ≤ n ≤ 100000，
数列中的元素的取值范围 [1,109]。

输入样例：

1 2	`6 2 3 4 5 6 1`

输出样例：

暴力解法思想

模仿人类的肉眼观察法，从左往右进行两个for循环的迭代。

暴力解法代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int q[N];

// 暴力解法
int main()
{
    
    int n; cin >> n;
    
    for(int i = 0; i < n; i++) cin >> q[i];
    
    int cnt = 0;
    
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            if(q[i] > q[j])
                cnt++;
                
    cout << cnt << endl;
    
    return 0;
}

如果使用暴力解法，结果是TLE，因此暴力解法不可行。

较优的方案：使用归并排序进行求解

知识回顾

二路归并排序

在归并排序的过程中进行统计

简单图示

2023-02-16_114608

细节处理

逆序对最多的情况：即倒序序列

此时有：

算法代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int q[N], temp[N];

LL merge_sort(int l, int r){
    
    if(l >= r) return 0;
    
    int mid = l + r >> 1;
    
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);// 核心代码1
    
    int i = l, j = mid + 1, k = 0;
    
    while(i <= mid && j <= r){
        if(q[i] <= q[j]) temp[k++] = q[i++];
        else {
            temp[k++] = q[j++];
            res += mid - i + 1;// 核心代码2
        }
    }
    
    while(i <= mid) temp[k++] = q[i++];
    while(j <= r) temp[k++] = q[j++];
    
    for(i = l, j = 0; i <= r; i++,j++) q[i] = temp[j];
    
    return res;
}

int main()
{
    
    int n; cin >> n;
    
    for(int i = 0; i < n; i++) cin >> q[i];
    
    cout << merge_sort(0, n - 1) << endl;
    
    return 0;
}