黑匣子

我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量I，在初始时刻，黑匣子为空且I等于0，这个黑匣子执行一系列的命令。有两类命令：
ADD(x)：把元素x放入黑匣子；
GET ： I 增1的同时，输出黑匣子内所有整数中第I小的数。牢记第I小的数是当黑匣子中的元素以非降序排序后位于第I位的元素。
现需要一个有效的算法处理给定的系列命令。ADD 和 GET 命令的总数至多各有30000个且每一个数的绝对值不超过200000。(注意：如果在执行GET 命令时I已经大于输入的数的个数，则输出0，I的值不变)
样例输入:
ADD(3)
GET
ADD(1)
GET
ADD(-4)
ADD(2)
ADD(8)
ADD(-1000)
GET
GET
ADD(2)
样例输出：
3 3 1 2

大概就是建两个堆。

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <queue>
 6 #include <cstdio>
 7 using namespace std ;
 8 priority_queue<int> Q1 ;
 9 priority_queue<int , vector<int> , greater<int> > Q2;
10 char a[15] ; int  num ;
11 
12 int main (  ) {
13 //    freopen( "10572.in" , "r" ,stdin ) ;
14 //    freopen( "10572.out", "w" ,stdout) ;
15     int nxt = 1 ;
16     while( ~scanf( "%s" , a ) ) {
17         if( a[0] == 'A' ) {
18             int l = 4 ; num = 1 ;
19             if( a[l] == '-' ) ++ l ;
20             num = a[l ++ ] - '0' ;
21             while( a[l] !=')' ) num = num*10 + a[l] - '0' , ++l ;
22             if( a[4] == '-' ) num = 0 - num ;
23             int tot = Q1.size(  ) ; 
24             if( tot < nxt ) {
25                 if( Q2.empty( ) ) Q1.push( num ) ;
26                 else if( num < Q2.top( ) ) Q1.push( num ) ;
27                 else { Q1.push( Q2.top( ) ) ; Q2.pop(  ) ; Q2.push( num )  ;}
28             }
29              
30             
31             else {    
32                 if( num > Q1.top( ) ) Q2.push( num ) ;
33                 else {
34                     Q2.push( Q1.top(  ) ) ;
35                     Q1.pop( ) ;
36                     Q1.push( num ) ;
37                 }
38             }
39             continue ;
40         }
41         int tot1 =Q1.size( ) ,tot2 = Q2.size(  ) ;
42         if( nxt  > tot1 + tot2 ) {
43             printf( "0 " ) ;
44             continue ;
45         }
46         if( nxt >= tot1 ) {
47             while( Q1.size( ) != nxt ) {
48                 Q1.push( Q2.top( ) ) ;
49                 Q2.pop(  ) ;
50             }
51             printf( "%d " , Q1.top( ) ) ;
52             nxt++ ;
53             continue ;
54         }
55     }
56     return 0 ;
57 }