洛谷 P1168 中位数

传送门

思路

昨天CKW大佬讲的题

用两个优先队列，一个大根堆，一个小根堆

保证小根堆里的数都比大根堆里的数要大，每次输入一个数，看这个树是否比大根堆的堆顶要大，如果比大根堆堆顶大的话放进小根堆中，否则放入大根堆中，如果两个堆中元素个数差大于了1，那就看看是哪个堆的元素更多一些，将这个元素的堆顶放到另一个堆中，保证了两个堆的堆顶之中一定有一个数是目前中位数，然后输出的时候看看哪个堆元素多输出哪个堆的堆顶就好了

需要注意的是，第一个数需要特殊处理，直接输出即可

还有就是，在洛谷上用\(size()\)函数不行，会\(CE\)，所以这里用了两个\(cnt\)

代码

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

inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    return x * f;
}

priority_queue<int> qb;
priority_queue<int, vector<int>, greater<int> > qs;
int n, topp, a, cnts, cntb;

int main() {
    n = read();
    topp = read();
    qb.push(topp);
    cntb++;
    cout << qb.top() << '\n';
    for(int i = 2; i <= n; i++) {
        a = read();
        if(a > qb.top()) qs.push(a), cnts++;
        else qb.push(a), cntb++;
        while(abs(cntb - cnts) > 1) {
            if(cntb > cnts) {
                qs.push(qb.top());
                cnts++;
                qb.pop();
                cntb--;
            }
            else {
                qb.push(qs.top());
                cntb++;
                qs.pop();
                cnts--;
            }
        }
        if(i & 1) printf("%d\n", cntb > cnts ? qb.top() : qs.top());
    }
    return 0;
}