AcWing 788. 逆序对的数量
原题链接
简单
作者:
lemon_242
,
2024-03-04 08:57:40
,
所有人可见
,
阅读 15
y总原样模板+注释理解
#include <iostream>
using namespace std;
typedef long long LL; //因为输出结果爆int,所以用long long
const int N = 1e5 + 10;
int a[N], tmp[N]; //归并排序中,需要一个临时数组在合并的时候来存最终结果
//merge_sort返回的是逆序对的数量,数据类型是long long
//merge_sort的写法本质是归并排序的模板,三步走
LL merge_sort(int q[], int l, int r)
{
//当传入的左边界>=右边界时,无需排序/排序结束,返回0
if (l >= r) return 0;
//任意取一个中间值,所以 mid = l + r >> 1
int mid = l + r >> 1;
//逆序对的数量由3部分组成,左半边逆序对的数量+右半边逆序对的数量+横跨左右的逆序对的数量
//这里先处理两个半边的逆序对的数量
//在计算得到逆序对的数量的同时,也是把左右两个数组排序的过程
LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
//k是结果数组tmp里的指针,用来协助放数字,从0开始往后走
//i,j分别代表左右两个排序好的数组的开头位置,准备合并结果
int k = 0, i = l, j = mid + 1;
//当两个数组都没有到尾巴时
while (i <= mid && j <= r)
//谁小把谁先放入结果数组tmp中,然后对应指针++
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else
{
//比起模版,多加了一行去计算res
//计算的逻辑是:如果q[i] > q[j],也就是else这个分支,此时会出现逆序对
//则左半边i指针对应的数字 之后一直到分界点mid之间的数字的个数,就是 当前 右半边j指针对应的数字的逆序对数量
res += mid - i + 1;
//计算完res后,谁小把谁先放入结果数组tmp中,然后对应指针++
tmp[k ++ ] = q[j ++ ];
}
//扫尾工作,也就是一边or左右两边数组 存在“到头”现象,剩下的只需要无脑加入结果数组中,不需要比大小了
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
//临时数组里的值放到原数组中去
//注意:这里q数组的起始不是0,而是l。因为不是到最后一步才“转存”排序结果,每次递归的结尾都“转存”了
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
return res;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
cout << merge_sort(a, 0, n - 1) << endl;
return 0;
}