AcWing 788. 逆序对的数量
原题链接
简单
作者:
Java同学
,
2022-06-23 23:03:18
,
所有人可见
,
阅读 142
详情看注释,最关键的问题用注释表出
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
// 为什么能够采用归并来计算 逆序对
// 因为归并是先分到最小 ,也就是左右两个数组分别只有一个数,那么此时下标和位置均没有变化
// 在进行 归并的时候 ,我们又同时对满足要求的逆序对数量进行添加,然后同时归并
// 归并到最后 也就是两个大的左右数组,内部均有序,而外部无序,虽然左右数组的内部位置发生了变化,但是由于递归已经把发生变化的部分计算完成了
// M 是右边数组的下界
long long res = 0;
void merge(int arr[], int L, int M, int R)
{
int left_len = M - L;
int right_len = R - M + 1;
int left_arr[left_len];
int right_arr[right_len];
for (int i = L; i < M; i++)
{
left_arr[i - L] = arr[i];
}
for (int j = M; j < R + 1; j++)
{
right_arr[j - M] = arr[j];
}
int i = 0;
int j = 0;
int k = L;
while (i < left_len && j < right_len)
{
if (left_arr[i] <= right_arr[j])
{
arr[k++] = left_arr[i++];
}
else
{
arr[k++] = right_arr[j++];
// 设想只有两个数的情况,这也是归并最开始 分而治之 分到只有两个数
// 前面的 if 属于 下标小于 且 数值也小于等于
// 这个判断中 ,则符合题目要求
// 那么根据归并排序的特点,块内有序,块间无序,所以这时候
// 左半边数组从i位置 到 M - 1位置 均大于当前右半边数组的 j位置(注意 M是右半边数组的下界)
// 注意 这里需要加上 L 这样才能保证下标正确 这就是对 i 进行一个下标矫正
// 也就是说 把 i + L 之后 这样 M 和 i+L均是在数组上的下标了
res += M - (L + i);
}
}
while (i < left_len)
{
arr[k++] = left_arr[i++];
}
while (j < right_len)
{
arr[k++] = right_arr[j++];
}
}
void merge_sort(int arr[], int L, int R)
{
if (L >= R)
{
return;
}
else if (L < R)
{
int M = (L + R) >> 1;
merge_sort(arr, L, M);
merge_sort(arr, M + 1, R);
merge(arr, L, M + 1, R);
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
merge_sort(arr, 0, n - 1);
// for (int i = 0; i < n; i++)
// {
// printf("%d ", arr[i]);
// }
cout << res;
return 0;
}