题目传送门
【题目大意】
读入一个整数序列，每当已经读入的整数个数为奇数时，输出已经读入的整数构成的序列的中位数。
【思路分析】
这题可以使用“对顶堆”的在线做法。为了动态维护中位数，我们可以建立两个二叉堆，一个小根堆、一个大根堆。在以此读入序列的过程中，设当前读入的序列长度为$L$，我们始终保持：
1.序列中从小到大排名为$1～\frac{M}{2}$的整数储存在大根堆中
2.序列中从小到到排名为$\frac{M}{2}+1～M$的整数储存在小根堆中
任何时候，如果某一个堆中元素过多，打破了这个性质，就取出该堆的堆顶插入另一个堆。这样就能保证序列的中位数为小根堆的堆顶。
重新读入一个整数$X$时，如果$X$小于当前的中位数，就插入大根堆，否则插入小根堆，在插入后检查并维护上述性质即可，这就是“对顶堆”算法。
【代码实现】
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #define rg register 5 #define go(i,a,b) for(rg int i=a;i<=b;i++) 6 using namespace std; 7 int T,m,n,mid; 8 priority_queue<int>q1;//小根堆 9 priority_queue<int,vector<int>,greater<int> >q2;//大根堆 10 int main(){ 11 scanf("%d",&T); 12 while(T--){ 13 scanf("%d%d",&m,&n);printf("%d %d\n",m,n/2+1); 14 while(q1.size()>0) q1.pop(); 15 while(q2.size()>0) q2.pop(); 16 go(i,1,n){ 17 int x;scanf("%d",&x); 18 if(i==1){mid=x;q2.push(x);} 19 else{ 20 if(x<mid)q1.push(x); 21 else q2.push(x); 22 } 23 while((int)q1.size()-(int)q2.size()>1){int y=q1.top();q1.pop();q2.push(y);} 24 while((int)q2.size()>(int)q1.size()){int y=q2.top();q2.pop();q1.push(y);} 25 mid=q1.top(); 26 if(i&1) printf("%d ",mid); 27 if((i&1)&&(i/2+1)%10==0) puts(""); 28 } 29 if((m/2+1)%10) puts(""); 30 } 31 return 0; 32 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11248741.html
