Solution

经典的动态维护序列中位数问题。

采用对顶堆做法：维护一个大根堆和一个小根堆，其中大根堆维护当前序列中较小的一半元素，小根堆维护较大的一半元素。依次插入每个元素：

• 若当前元素小于小根堆堆顶，则插入大根堆。
• 若当前元素大于等于小根堆堆顶，则插入小根堆。

每插入一个元素，检查当前两个堆的大小之差是否超过 ，若超过 ，则调整为相等大小。这样，每到序列有奇数位时，元素较多的堆的堆顶即为当前序列的中位数。

时间复杂度： 。

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int s,t,n,x;
int fr(){
    char ch;
    int sum,sign=1;
    while((ch=getchar())>'9'||ch<'0')
        if(ch=='-')
            sign=-1;
    sum=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        sum=(sum<<3)+(sum<<1)+ch-'0';
    return sum*sign;
}
int main(){
    t=fr();
    while(t--){
        s=fr(); n=fr();
        printf("%d %d\n",s,n+1>>1);
        priority_queue<int,vector<int>,greater<int> >q1;
        priority_queue<int,vector<int>,less<int> >q2;
        x=fr();
        printf("%d ",x);
        q1.push(x);
        for(int i=2;i<=n;i++){
            x=fr();
            if(q1.top()>=x)
                q2.push(x);
            else
                q1.push(x);
            if(q1.size()>q2.size()+1){
                q2.push(q1.top());
                q1.pop();
            }
            else if(q1.size()+1<q2.size()){
                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;
}