题目描述
给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。
输入格式
第一行包含整数n,表示数列的长度。
第二行包含 n 个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
1≤n≤100000
我的思路
逆序对:下标 i < j a[i] > a[j],那么这就是一对逆序对;在归并排序中,当a[i] <= a[j] 时,符合升序的排序;当a[i] > a[j]时,就有mid - i + 1 个逆序对(对于j位置的数来说),所以当我们的j从mid + 1,遍历到了r时,这两个区间的逆序对就找完了;所以对于找一个序列中的逆序对的个数,只用在归并排序的模板中的a[i] < a[j] tmp[k] = p[j], 后面添加一句:ans += mid - i + 1;就搞定了这个问题。注意:ans 的类型应该为long long ,因为当n取到了1e5时,逆序对的极限的个数是会超过2e9的。粗略的计算大概有 n * (n - 1) / 2 个,大概是5e9个。
样例
输入样例:
6
2 3 4 5 6 1
输出样例:
5
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e6 + 50;
int a[maxn], tmp[maxn];
long long ans;
inline void merge_sort(int p[], int l, int r) {
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(p, l, mid);
merge_sort(p, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r) {
if(p[i] <= p[j]) tmp[k++] = p[i++];
else tmp[k++] = p[j++], ans += mid - i + 1;
}
while(i <= mid) tmp[k++] = p[i++];
while(j <= r) tmp[k++] = p[j++];
for(int i = l, k = 0; i <= r; i++, k++) p[i] = tmp[k];
}
int main(void) {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
merge_sort(a, 1, n);
printf("%lld\n", ans);
return 0;
}