输入一个 n 个数的序列 {a1, a2, a3, ...., an} ,
求序列的逆序对数,即有多少个有序对 (i, j) 满足 i < j 且 aᵢ > aⱼ ,其中 n ≤ 10⁶ 。
【输入描述】
输入两行。第一行为元素个数 n ;第二行是每个元素的值;
【输出描述】
输出一行。输出逆序对的数量。
【输入样例】
6
5 1 4 6 3 2
【输出样例】
9
【参考程序】
//爱码岛编程
#include <bits/stdc++.h>
using namespace std;
int arr[10001], ans = 0;
//合并
void merge(int arr[], int left, int mid, int right, int temp[]) {
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j])
temp[t++] = arr[i++];
else {
temp[t++] = arr[j++];
// 统计个数
ans += mid - i + 1;
}
}
while (i <= mid)
temp[t++] = arr[i++];
while (j <= right)
temp[t++] = arr[j++];
t = 0;
i = left;
while (i <= right) {
arr[i++] = temp[t++];
}
}
void mergeSort(int arr[], int left, int right, int temp[]) {
if (left < right) {
int mid = left + (right - left) / 2;
//分
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
//合
merge(arr, left, mid, right, temp);
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
//调用归并排序函数
int temp[n];
mergeSort(arr, 0, n - 1, temp);
cout << ans << endl;
return 0;
}