每日一题 4月9日 Running Median 动态中位数

思路：用两个优先队列，一个维护大的一半，一个维护小的一半。然后就可以了。

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

int main(){

    int t; scanf("%d", &t);
    while(t--){

        priority_queue<int> q1;
        priority_queue<int, vector<int>, greater<int> > q2;
        int id, n, x; scanf("%d%d", &id, &n);
        printf("%d %d\n", id, (n+1)/2);
        scanf("%d", &x); printf("%d ", x); q1.push(x);
        for(int i=2; i<=n; i++){
            scanf("%d", &x);
            if(x<q1.top()) q1.push(x);
            else q2.push(x);
            if(q1.size()>q2.size()+1){
                q2.push(q1.top());
                q1.pop();
            }
            if(q2.size()>q1.size()+1){
                q1.push(q2.top());
                q2.pop();
            }
            if(i%2==1){
                if(q1.size()>q2.size()){
                    printf("%d ", q1.top());
                }
                else{
                    printf("%d ", q2.top());
                }
            }
            if(i%20==0) printf("\n");
        }
        printf("\n");
    }

    return 0;
}