题目描述
给定一个长度为 n 的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i[HTML_REMOVED]a[j],则其为一个逆序对;否则不是。
算法1
$O(nlogn)$
此题用归并排序可以AC也说明归并排序分治我们求的是从小到大的顺序,逆序对恰好是逆序数量
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N], tmp[N]; //tmp数组用来记在排序过程中排好的数字
int n;
LL merge_sort(int q[], int l, int r)
{
if(l >= r) return 0; //如果指针错位,说明排好序了,返回即可
int mid = l + r >> 1;
LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1; //k表示tmp数组的下标,i表示左边区间的左端点,mid + 1表示右边区间的左端点
while(i <= mid && j <= r) //如果两边都没排完
{
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; //如果q[i] <= q[j], 把q[i]放入tmp数组中,i++,k++;
else
{
res += mid - i + 1; //(q[i], q[j])是逆序对,并且q[i]....q[mid] 与q[j] 形成 mid-i+1个逆序
tmp[k ++ ] = q[j ++ ]; //反之把q[j]放入tmp数组中,j++,k++;
}
}
while(i <= mid) tmp[k ++ ] = q[i ++ ]; //如果右区间已经全在tmp里,但左区间没排完,则把左区间放入tmp
while(j <= r) tmp[k ++ ] = q[j ++ ]; //同理放入右区间,
//这两个循环只会有一个被执行
for (int i = l, j = 0; i <= r; i++, j ++) q[i] = tmp[j]; //把排好的值重新赋回原数组
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
cout << merge_sort(a, 0, n - 1) << endl;
return 0;
}