算法
(归并排序) O(nlogn)
容易想到冒泡排序的机制正好是利用消除逆序来实现排序的,也就是说,交换相邻两个逆序数,最终实现整个序列有序,那么交换的次数即为逆序对的数量。但由于冒泡排序的时间复杂度是O(n2),在这题中肯定过不去。然后注意到我们学过的归并排序也能统计逆序对,时间复杂度是O(nlogn)。我们只需略微修改原有归并排序,当右边序列的元素为较小值时,就统计其产生的逆序对数量,即可完成逆序对的统计。
最后,注意要开long long
!!!
C++ 代码
#include <iostream>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n, ans;
int a[N], r[N];
void msort(int s, int t) {
if (s == t) return; // 如果只有一个数字则返回,无须排序
int mid = (s + t) / 2;
msort(s, mid); // 分解左序列
msort(mid + 1, t); // 分解右序列
int i = s, j = mid + 1, k = s; // 接下来合并
while (i <= mid && j <= t) {
if (a[i] <= a[j]) r[k] = a[i], k++, i++;
else {
r[k] = a[j], k++, j++;
ans += mid - i + 1; // 统计产生逆序对的数量
}
}
while (i <= mid) { // 复制左边子序列剩余
r[k] = a[i], k++, i++;
}
while (j <= t) { // 复制右边子序列升序
r[k] = a[j], k++, j++;
}
for (int i = s; i <= t; ++i) a[i] = r[i];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
msort(1, n);
cout << ans << '\n';
return 0;
}