P1177快速排序 题解

· · 个人记录

众所周知，A+B Problem 的题解里充斥着各种奇奇怪怪的做法，那为什么这道题没有呢？于是就有了这篇题解。

1.set大法好

我们都知道，STL 有 sort 和 priority_queue 给我们用，但却很少人想到 set 也是可以排序的。由于有重复元素，所以这里使用 multiset。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n,x;
    multiset<int> s;
    cin>>n;
    while(n--) {cin>>x;s.insert(x);}
    for(int t:s) cout<<t<<" ";
    return 0;
}

虽然非常“巧妙”，但是这使用了 STL，违背了题目要求，于是：

2.桶排序

我们都知道，桶排序是非常快的，只需要 O(N) 的时间和 O(a_i) 的空间，然而这题 a_i 最大到了 10^9，面对这种情况，最常见的选择就是是离散化（迫真）。于是，我们先对数组离散化一下，再把数组中元素的离散化结果扔到桶里面，最后扫一遍桶中元素即可。

#include<bits/stdc++.h>
using namespace std;
int n,a[100010],b[100010],cnt=0;
int t[100010];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        b[++cnt]=a[i];
    }
    sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-b-1;
    for(int i=1;i<=n;i++) {
        int tmp=lower_bound(b+1,b+cnt+1,a[i])-b;
        t[tmp]++;
    }
    for(int i=1;i<=cnt;i++)
        while(t[i]--)
            cout<<b[i]<<" ";
    cout<<endl;
    return 0;
}

你可能会问：这不是还是需要 sort 吗？没错，但你还是不能否认桶排序就是快（实际上，这是本篇题解中最快的做法了）。

但是，使用了 sort 确实违背了题目要求，于是：

3.动态开点权值线段树

这题不是显然可以用权值线段树做吗。。。由于数据范围比较大，要么离散化要么动态开点。如果离散化，就需要 sort，这违背了我们的初衷，所以我们使用动态开点。

首先依次加入 n 个数，接下来每次询问排名为 i 的数即可，时间复杂度 O(nlog(n))。

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int n,tot=0,root;
struct tree{int num,l,r,lson,rson;} t[2000010];
#define mid (t[now].l+t[now].r)/2
int newnode(int l,int r) {
    t[++tot].l=l,t[tot].r=r;
    return tot;
}
void change(int &now,int x,int l=-inf,int r=inf) {
    if(!now) now=newnode(l,r);
    if(l!=r) {
        if(x<=mid) change(t[now].lson,x,l,mid);
        else change(t[now].rson,x,mid+1,r);
    }
    t[now].num++;
}
int search(int now,int k) {
    if(t[now].l==t[now].r) return t[now].l;
    int val=t[t[now].lson].num;
    if(k<=val) return search(t[now].lson,k);
    else return search(t[now].rson,k-val);
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x;
        cin>>x;
        change(root,x);
    }
    for(int i=1;i<=n;i++)
        cout<<search(root,i)<<" ";
    cout<<endl;
    return 0;
}

这种做法非常完美的满足了题目的要求：不用任何 STL。完结撒花！