P1168

Aryper · 2021-08-08 14:18:25 · 个人记录

中位数

搞一个小根堆和一个大根堆分别维护。

这样中位数就是两个堆的堆顶之一。

当两个堆的大小之差大于 1 时维护平衡即可。

时间复杂度 O(n\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#define ll long long
using namespace std;

ll n,x;

priority_queue<ll,vector<ll> > q1;

priority_queue<ll,vector<ll>,greater<ll> > q2;

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int main() {

    n=read();q1.push(read());
    write(q1.top());putchar('\n');

    for(ll i=2;i<=n;i++) {
        x=read();
        if(x>q1.top()) q2.push(x);
        else q1.push(x);
        if(q1.size()>q2.size()&&q1.size()-q2.size()>1) {q2.push(q1.top());q1.pop();}
        if(q2.size()>q1.size()&&q2.size()-q1.size()>1) {q1.push(q2.top());q2.pop();}
        if(i%2==1) {
            if(q1.size()>q2.size()) write(q1.top());
            else write(q2.top());
            putchar('\n');
        }
    }

    return 0;
}