(p.s.)我也不知道为什么我当时的代码那么挫，各位看官就凑合着看吧。
这题的思路特别的套路，找中位数，我们可以用对顶堆。
求中位数，我们可以用两个堆来维护，一个大根堆，一个小根堆。
用大根堆维护 (1 hicksim frac{n}{2}) 的数，用小根堆维护 (frac{n}{2} + 1 hicksim n) 的数。
当 (n) 是奇数时，小根堆的堆顶就是中位数；当 (n) 是偶数时，中位数就是小根堆和大根堆的较小值。
但是我的代码写的太挫了，所以我觉得我有必要讲一下，我们设 (mid) 为中位数。
我在插入 (x) 的时候，如果 (x>mid) 则将 (x) 插入小根堆，否则插入大根堆，但是这样会导致大根堆的大小和小根堆的大小相差过多。
所以，我添了一个 (operatorname{change}) 函数来通过转移堆顶维护大、小根堆的大小大致相等：
void change(){
if(qx.size()<qd.size()){
while(qx.size()<qd.size()){
qx.push(qd.top());
qd.pop();
}
}
if(qx.size()>qd.size()+1){
while(qx.size()>qd.size()){
qd.push(qx.top());
qx.pop();
}
}
}
在判断中位数的时候，我们只需要比较大根堆堆顶和小根堆堆顶的大小，输出较小值并删除就好了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
priority_queue<int>qd;
priority_queue<int,vector<int>,greater<int> >qx;
int p,mid=-INT_MAX,mid2;
int hd,m,ans[10001],x;
void change(){
if(qx.size()<qd.size()){
while(qx.size()<qd.size()){
qx.push(qd.top());
qd.pop();
}
}
if(qx.size()>qd.size()+1){
while(qx.size()>qd.size()){
qd.push(qx.top());
qx.pop();
}
}
}
int main(){
scanf("%d",&p);
for(int i=1;i<=p;i++){
memset(ans,0,sizeof(ans));
int num=0,x;
while(qd.size()!=0) qd.pop();
while(qx.size()!=0) qx.pop();
while(scanf("%d",&x)){
if(x==0) break;
if(x>0){
if(x>mid) qx.push(x);
else qd.push(x);
change(); mid=qx.top();
}
else{
if(qx.size()==qd.size()){
mid2=qd.top();
if(mid<=mid2){
printf("%d
",mid);
qx.pop(); change();
mid=qx.top();
}
else{
printf("%d
",mid2);
qd.pop(); change();
mid=qx.top();
}
}
else{
printf("%d
",mid);
qx.pop(); change();
mid=qx.top();
}
}
}
}
return 0;
}