Thinking Process

一道动态中位数的题。
用一个大根堆的优先队列存一半较小值，用一个小根堆的优先队列存一半较大值。

  1. 如果x小于小根堆的堆顶，则意味着它应该在大根堆中
  2. 否则，则意味着它应该在小根堆中

最后一步，判断两个优先队列的大小是否相差1，如果正好相差1，哪个优先队列大，就输出哪个的top，否则的话需要修改至相差为1

Code

#include<iostream>
#include<queue>
#include<string.h>
#include<vector>
using namespace std;

int t, m;

int main() {
    cin >> t;
    while(t --) {
        priority_queue<int, vector<int>, greater<int> > qa;    // small heap
        priority_queue<int, vector<int>, less<int> > qb;       // big heap
        int s, n;
        cin >> s >> n;
        int x;
        cin >> x;
        printf("%d %d\n", s, (n + 1) >> 1);
        printf("%d ", x);
        qa.push(x);
        for(int i = 2;i <= n ;i ++) {
            cin >> x;
            if(x <= qa.top()) qb.push(x);
            else qa.push(x);
            if(qa.size() > qb.size() + 1) {
                qb.push(qa.top());
                qa.pop();
            } else if(qb.size() > qa.size() + 1) {
                qa.push(qb.top());
                qb.pop();
            }
            if(i % 2 == 1) { 
                if(qa.size() > qb.size()) printf("%d ", qa.top());
                else printf("%d ", qb.top());
            }
            if(i % 20 == 0) printf("\n");
        }
        printf("\n");
    } 
}