这道题我使用的是归并排序, 而且只在归并排序上加一句话即可
题目:逆序对
先来回忆一下归并排序的原理:
有数列:2 7 5 4 9 8 6
利用归并排序:
先二分:
2 7 5 4 9 8 6
再分开排序:
2 4 5 7 6 8 9
取第一个数列第一个数与第二个数列第一个数进行比较,取较小的一个数加入一个临时数组,而后删除这个数:
4 5 7 6 8 9
重复以上步骤得:
8 9
会发现此时第二个数组还有两数,而第一个数列已被弹空,此时就直接将第二个数列的所有剩下的加入临时数组,最后再将临时数组里的数一一赋值给原数组
回到“取第一个数列第一个数与第二个数列第一个数进行比较,取较小的一个数加入一个临时数组,而后删除这个数”这一步:
4 5 6 6 8 9
2
想想逆序对定义:
逆序对就是序列中ai > aj且i < j的有序对
那么如果2比在6前且2比6小,所以2便能与6组成一对逆序对,而由于第二个数列已经排序好, 所以6后的数一定大于6, 于是后面的数8 9也一定能与2组成逆序对
其他同理(自己试试其他数)
所以当归并排序完后, 逆序对也求出来了
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000001], b[1000001], n, ans;
void mergesort(ll l, ll r) { if(l >= r) return ; ll m = l + (r - l) / 2; mergesort(l, m); mergesort(m + 1, r); ll l1 = l; ll l2 = m + 1; ll lb = l; while(l1 <= m || l2 <= r) { if(l1 > m) {b[lb ++] = a[l2]; l2 ++;} else if(l2 > r) {b[lb ++] = a[l1]; l1 ++;} else { if(a[l1] < a[l2]) {b[lb ++] = a[l1]; l1 ++;} else {b[lb ++] = a[l2]; l2 ++; ans += m - l1 + 1;} } } for(int i = l; i <= r; i ++) { a[i] = b[i]; } }
int main() { cin >> n; for(int i = 1; i <= n; i ++) { cin >> a[i]; } mergesort(1, n); cout << ans ; return 0; }
|