AcWing 788. 逆序对的数量
原题链接
简单
作者:
doubleq
,
2021-05-17 23:05:25
,
所有人可见
,
阅读 303
求逆序对
输入样例
6
2 3 4 5 6 1
输出样例
5
(暴力枚举) $O(nlogn)$
C++ 代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//2 3 4 1 5 6
const int N = 100010;
int a[N],temp[N];
int n;
long long res;//注意数量会爆int
void merge_sort(int l,int r)
{
if(l >= r) return;
int mid = l + r >> 1;
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]) temp[k ++] = a[i ++];
else temp[k ++] = a[j ++],res += mid - i + 1;//从i开始到mid处即为l~r之间的逆序对,其余与归并排序相同
}
while(i <= mid) temp[k ++] = a[i ++];
while(j <= r) temp[k ++] = a[j ++];
for(int i = l,j = 0;j < k;i ++,j ++) a[i] = temp[j];
}
int main()
{
scanf("%d",&n);
for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
merge_sort(0,n - 1);
cout << res;
return 0;
}