Home 求逆序对: AcWing 107 超快速排序
Post
Cancel

求逆序对: AcWing 107 超快速排序

Link

仔细想想, 这道题就是求逆序对. 再就是注意结果要用 long long.

归并排序解法

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,a[500010],b[500010];
long long ans;
void merge(int l,int r){
    if(r<=l) return;
    int mid=l+((r-l)>>1);
    merge(l,mid),merge(mid+1,r);
    for(int i=l,j=mid+1,k=l;k<=r;++k){
        if(i<=mid&&j<=r&&a[i]>a[j]){
            ans+=mid-i+1;
            b[k]=a[j++];
        }else if(j==r+1||(i<=mid&&a[i]<=a[j])) b[k]=a[i++];
        else b[k]=a[j++];
    }
    for(int i=l;i<=r;++i) a[i]=b[i];
}
int main() {
    while(scanf("%d",&n)&&n){
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        ans=0;
        merge(1,n);
        printf("%lld\n",ans);
    }
    return 0;
}

树状数组解法

可以参考一篇博客: 树状数组求逆序对

This post is licensed under CC BY 4.0 by the author.

对顶堆的应用: AcWing 106 动态中位数

线段树和树状数组