题目描述
给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。
样例
6
2 3 4 5 6 1
解题方法
本题为求逆序数对个数,“有求解逆序对问题,实际上有三种算法可以处理,分别是冒泡算法,归并排序,以及树状数组求解,这里显然我们可以用性价比最高,代码最好写,效率特高的归并排序算法.”
在分治后的每一层合并中顺便求出逆序对数量是这个题想法的由来,归并排序分治我们求的是从小到大的顺序,我们所求的逆序对恰好是逆序数量,与归并排序不谋而合。
mid - i + 1解释:例如[3,4,1,2]中q[0]>q[2],则q[0],q[1]都与q[2]成逆序对,而q[mid]与q[i]有mid+1-i个数字,因此逆序对增加mid-i+1
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int q[N], a[N];
LL merge_sort(int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
LL cnt = merge_sort(l, mid) + merge_sort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) a[k++] = q[i++];
else {
a[k++] = q[j++];
cnt += mid - i + 1;
}
while (i <= mid) a[k++] = q[i++];
while (j <= r) a[k++] = q[j++];
for (int i = l, j = 0; i <= r; i++, j++) q[i] = a[j];
return cnt;
}
int main () {
cin >> n;
for (int i = 0; i < n; i++) cin >> q[i];
cout << merge_sort(0, n - 1);
return 0;
}