AcWing 788. 逆序对的数量
原题链接
简单
作者:
tq
,
2024-04-13 15:02:33
,
所有人可见
,
阅读 4
//第二遍想不到
//每次排序,指针j每后移一次之后,第一个区间i之后的数(此时q[i]>q[j]),均大于q[j],所以每次都有mid - i + 1对逆序数
#include <iostream>
using namespace std;
typedef long long LL; //最多逆序对n(n-1)/2 会爆int
const int N = 100010;
int a[N], tmp[N]; //全局变量如果定义了,就不需要写在函数形参
LL merge_sort(int l, int r){
if(l >= r) return 0; //这里是返回结果为0
int x = l + r >> 1;
// merge_sort(l, x);
// merge_sort(x + 1, r);
//忘了将两组相加
LL res = merge_sort(l, x) + merge_sort(x + 1, r);
int i = l, j = x + 1, k = 0;
while(i <= x && j <= r){
if(a[i] <= a[j]) tmp[k ++] = a[i ++]; //少写等于号 a[i] <= a[j] 等于时i也要后移,否则相等两数也算逆序数了
else {tmp[k ++] = a[j ++]; res += x - i + 1;}
}
//忘记扫尾 并且位置应该放在这次函数的循环(为了排序)之后
while(i <= x) tmp[k ++] = a[i ++];
while(j <= r) tmp[k ++] = a[j ++];
for(int i = l, j = 0; i <= r; i ++, j ++) a[i] = tmp[j];
return res;
}
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
printf("%lld", merge_sort(0, n - 1));
return 0;
}