记录一下自己写的一个简单的对顶堆的模板。

题目描述

见题面。

样例

见题面

算法

解决中位数的算法，蓝书上说了两种，此处给出动态算法，对顶堆算法。

时间复杂度

$O(nlogn)$

参考文献

蓝书，lyd。

C++ 代码

#include <bits/stdc++.h>
#define oj
using namespace std;

priority_queue<int, vector<int>,greater<int> >minh;
priority_queue<int> maxh;

void solve(int x){
    if((maxh.size()==0&&minh.size()==0)||maxh.top()>=x){//第一个条件是为了保证不会出现数据的逆序
        maxh.push(x);
    }else {
        minh.push(x);
    }

    if (minh.size()<maxh.size()) {//保证小根堆的大于大根堆的
        minh.push(maxh.top());
        maxh.pop();
    }else{
        if(minh.size()==maxh.size()+2){//保证中位数位置
            maxh.push(minh.top());
            minh.pop();
        }
    }
}

int getans(){
    return minh.top();
}

int main(){
    #ifndef oj
    freopen("data.in", "r", stdin);
    freopen("oj.out", "w", stdout);
#endif

    int p,n;
    cin >> p;
    while(p--) {
        int id;
        cin >> id>>n;
        while (maxh.size()) {
            maxh.pop();
        }
        while (minh.size()) {
            minh.pop();
        }
        printf("%d %d\n", id, (n + 1) >> 1);
        for (int i=1; i<=n; i++) {
            int x;
            scanf("%d", &x);
            solve(x);   
            if(i%2){
                int ans = getans();
                printf("%d", ans);
                if(((i+1)>>1)%10){
                    printf(" ");
                }else {
                    printf("\n");
                }
            }
        }
        if(((n+1)>>1)%10)
        printf("\n");
    }
    return 0;
}