1.787. 归并排序 - AcWing题库
① 确定分界点 mid = l + r >> 1
② 递归排序 左边右边
③ 合并有序数组
模板:
void merge_sort(int q[], int l, int r){
if(l >= r) return 0;
int mid = l + r >> 1;
merge_sort(q, l ,mid), merge_sort(q, mid+1, r);
int i = l, j = mid+1, k =0;
// 归并
while(i <= mid && j <= r)
if(q[i] < q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
// 扫尾
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
// 物归原主
for(int i = l, j = 0; j < k; i++, j++) q[i] = tmp[j];
}
int main(){
merge_sort(q, 0, n-1);
}
tmp数组用来存放有序的部分
2.788. 逆序对的数量 - AcWing题库
首先看题目,知道什么是逆序数对。
可以一边归并排序一边计算有序数对
当i > j 并且 q[i] < q[j]的时候,因为这两部分都是有序数组。那么对于q[j]这个点,q[i]以后所有的数都可以跟q[j]构成逆序数对,所以针对q[j]这个数字可以构成的逆序数对有 res = mid - i + 1 个,让然后左右两边都这么递归计算就好。
注意题目的范围是100000,当最差的情况是这个数组是逆序的,等差数列求和算一下逆序对数量会超过INT_MAX
#include<iostream>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll q[N], tmp[N];
ll merge_sort(ll l, ll r){
if(l >= r) return 0;
ll mid = l + r >> 1;
ll res = merge_sort(l, mid) + merge_sort(mid+1, r);
ll i = l, j = mid+1, k = 0;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k++] = q[i++];
else{
tmp[k++] = q[j++];
res += mid - i + 1;
}
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(int i = l, j = 0; j < k; i++,j++) q[i] = tmp[j];
return res;
}
int main(){
ll n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> q[i];
}
ll res = merge_sort(0, n-1);
cout << res;
}