Running Median

进阶指南原题(对顶堆一下.),原来快读可以减少空间.

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

int main()
{
    int T;T=read();
    while(T--)
    {
        priority_queue<int,vector<int>,greater<int> >q;//mid+1->max
        priority_queue<int,vector<int>,less<int> >Q;//mid->min
        int id,n;id=read();n=read();
        printf("%d %d\n",id,(n+1)/2);
        for(int i=1;i<=n;i++)
        {
            int x;x=read();
            if(Q.size()>q.size())//推到q
            {
                if(!Q.size()||x>=Q.top())    q.push(x);
                else
                {
                    int y=Q.top();Q.pop();
                    Q.push(x);q.push(y);
                }
            }
            else//推到Q
            {
                if(!q.size()||x<=q.top())    Q.push(x);
                else
                {
                    int y=q.top();q.pop();
                    Q.push(y);q.push(x);
                }
            }
            if(i&1)
            {
                printf("%d ",Q.top());
            }if(i%20==0) puts("");
        }puts("");
    }
    return 0;
}