【算法】【归并排序】AcWing 算法基础 788. 逆序对的数量

题目

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

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例：

6 2 3 4 5 6 1

输出样例：

5

来源：AcWing 算法基础 788. 逆序对的数量

思路（注意事项）

题解

#include<iostream>

using namespace std;

typedef long long LL;  // 定义 long long 类型为 LL，方便使用

const int N = 100001;  // 定义数组的最大长度

int n;  // 数组的长度
int a[N], tmp[N];  // a[] 是原始数组，tmp[] 是归并排序时使用的临时数组

// 归并排序函数，返回区间 [l, r] 内的逆序对数量
LL merge_sort(int l, int r)
{
    if (l >= r) return 0;  // 如果区间只有一个元素或没有元素，逆序对数量为 0
    
    int mid = l + r >> 1;  // 计算区间的中点
    LL rep = merge_sort(l, mid) + merge_sort(mid + 1, r);  // 递归计算左右两半的逆序对数量
    
    int k = 0, i = l, j = mid + 1;  // k 是 tmp 数组的索引，i 和 j 分别是左右两半的起始索引
    while (i <= mid && j <= r)  // 合并左右两半
    {
        if (a[i] <= a[j])  // 如果左半部分的元素小于等于右半部分的元素
            tmp[k++] = a[i++];  // 将左半部分的元素放入 tmp 数组
        else  // 如果右半部分的元素小于左半部分的元素
        {
            tmp[k++] = a[j++];  // 将右半部分的元素放入 tmp 数组
            rep += mid - i + 1;  // 增加逆序对的数量，因为 a[j] 比 a[i..mid] 都小
        }
    }
    
    // 将剩余的元素放入 tmp 数组
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    
    // 将 tmp 数组中的元素复制回原数组 a
    for (i = l, k = 0; i <= r; i++, k++) a[i] = tmp[k];
    
    return rep;  // 返回当前区间的逆序对数量
}

int main()
{
    cin >> n;  // 输入数组的长度
    for (int i = 0; i < n; i++) cin >> a[i];  // 输入数组的元素
    
    LL sum = merge_sort(0, n - 1);  // 调用归并排序函数，计算逆序对的总数
    cout << sum;  // 输出逆序对的总数
    
    return 0;
}

纯代码

#include<iostream>

using namespace std;

typedef long long LL; 

const int N = 100001;

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

LL merge_sort (int l, int r)
{
	if (l >= r) return 0;
	
	int mid = l + r >> 1;
	LL rep = merge_sort (l , mid) + merge_sort (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  
		{
			tmp[k ++] = a[j ++];
			rep += mid - i + 1;
		}
		
	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 rep;
}

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