【算法】【归并排序】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;  // 如果区间只有一个元素或没有元素，逆序对数量为 0int 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 数组中的元素复制回原数组 afor (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;
}