Design a container, which has two kinds of operation, push and pop.
  Push: You should push the given number into the container.
  Pop: Please find the middle number of the container. If these is n numbers in container, it will be the (n+1)/2-th num when sort increased. Then pop the number.

The input contains one or more data sets. At first line of each input data set is an integer N (1<= N <= 100000) indicate the number of operations. 
  Then N lines follows, each line contains a number (0 or 1). "0" means a push operation, it's followed by an integer E. "1" means a pop operation.
  You may assume all the numbers in the input file will be in the range of 32-bit integer.

For each pop operation, you should print the integer popped. Please print "No Element!", if there is no number to pop. Please print a blank line after each data set.

9
0 10
0 -10
0 5
1
1
0 2
1
1
1
3
0 2
0 1
1

5
-10
2
10
No Element!

1

syu

Developing School's Contest 6

算法：

用两个优先队列实现。

队列A存比中间值小的数，优先大的； 定义A的最前面那个数为middle

队列B存比中间值大的数，优先小的。

动态维护这两个队列。 //当a比b个数多2时a.top()移到b中去，当b比a多1时，b.top()的值移到a中去。用两个变量len1，len2记录队列的长度。

这里的数据量比较大，应该用scanf来处理数据，用cin会超时：

post code 正确代码：

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
priority_queue<int>maxmin; //优先队列默认从大到小
priority_queue<int, vector<int>, greater<int> >minmax; //定义优先队列从小到大 
int len1=0,len2=0;
int flag=0;
int main()
{
      int x,i,judge,num,middle;
      while(scanf("%d",&x)!=EOF)
      {
         
         while(maxmin.empty()==0)maxmin.pop();    //清空队列
         while(minmax.empty()==0)minmax.pop();
          flag=len1=len2=0;
          for(i=1;i<=x;i++)
          {
            scanf("%d",&judge);                                     
             if(judge==1){                                   //进行pop操作
                          if(len1==0&&len2==0)flag=0; //如果两个队列的长度都为0，那么flag=0 @
                          if(flag==0){cout<<"No Element!"<<endl;continue;}  //flag=0 输出没有元素
                          cout<<middle<<endl;
                          maxmin.pop();len1--;
                           if(len1==0&&len2==0)flag=0;   //这里必须还得进行一次@的判断 防止出先多次容器有到空时的情况
                          if(len1!=0)middle=maxmin.top();  //对队列进行动态维护
                          if(len2-len1==1){num=minmax.top();
                                           minmax.pop();
                                           len1++;len2--;
                                           maxmin.push(num);
                                           middle=maxmin.top();
                                           } 
                         }              
             if(judge==0){
                          
                          scanf("%d",&num);      //当都为空时 的特殊操作
                          if(flag==0){middle=num;maxmin.push(middle);len1++;flag=1;continue;}  
                          flag=1;
                          if(num<=middle){len1++;maxmin.push(num);}
                          if(num>middle){len2++;minmax.push(num);}
                     //push时动态维护数据
                          if(len1-len2==2){num=maxmin.top();maxmin.pop();len1--;len2++;minmax.push(num);middle=maxmin.top();}
                          if(len2-len1==1){num=minmax.top();minmax.pop();len1++;len2--;maxmin.push(num);middle=maxmin.top();}
                          }
                           
                           
          }          
                   cout<<endl;
                   
                   
      }
    
    
    
}

附两组测试数据：

11

0 2
1
0 4
1
0 3
1
0 3
1
0 3
1
1

22

0 3
0 5
0 4
0 6
1
1
0 3
1
1
1
1
0 2
1
0 4
1
0 3
1
0 3
1
0 3
1
1