（对顶堆）SP15376 RMID - Running Median

一、算法分析

题意很显然，要求在线动态维护中位数。这时要用到对顶堆思路，即既然我们是每次取中位数，那就要涉及从中间取数，这样我们设置一个大顶堆，一个小顶堆，把两个堆的堆顶“挨”在一起，维持两个堆的大小相等或最多相差1（因为可能总数是奇数个）这样中间的数就一定是从两个堆的堆顶产生了。难点在于维护的过程。

其实个人对这个对顶堆的维护，个人理解是这样的，想象自己有一条绳子，绳子从中间分开，左边是大顶堆，右边是小顶堆，当输出前，先“拉绳子”，以样例输入为例。

代码及注释

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
priority_queue<int>bg;                              //大根堆 
priority_queue<int,vector<int>,greater<int> >sm;    //小根堆 
int p; 
inline int read(){                                  //本题对时间要求比较紧，加一个快读 
  char ch=getchar();
	int ans=0,f=1;
  while(ch<'0'||ch>'9'){
	  if(ch=='-') f=-1;
		ch=getchar();
	}
  while(ch>='0'&&ch<='9'){
	  ans=ans*10+ch-'0';
		ch=getchar();
	}
  return ans*f;
}
int main(){

  while(scanf("%d",&p)!=EOF){         //无脑读入 
  	while(!bg.empty()) bg.pop();
  	while(!sm.empty()) sm.pop();
  	bg.push(p);
  	while(p=read()){
  		if(p!=-1){                      //对于插入的情况 
  			if(p>=bg.top()){
  				sm.push(p);
				}
				else bg.push(p);
			}
			else{                           //先拉绳子，再取中位数 
				while(sm.size()>=bg.size()+1){ //当右边比左边大多于一个的时候，“拉左边绳子” 直到比如左边右边都是k个，或者左边是k个，右边k+1个（因为总是可能出现总共奇数个情况，但是我们倾向于从绳子最顶上那两个中的左边那个取中位数 
					bg.push(sm.top());
					sm.pop();                   //往左拉绳的操作 
				}
				while(bg.size()>sm.size()+1){
					sm.push(bg.top());
					bg.pop();                   //往右拉的操作 
				}
				printf("%d\n",bg.top());
				bg.pop();
			}
		}
		printf("\n");
	}
  
  
	return 0;	
} 

注意本题对时间限制较大，不能用cin和cout