http://acm.zjut.edu.cn/ShowContestProblem.aspx?ShowID=优先队列&MID=528
View Code
1 #include<iostream>
2 #include<stdio.h>
3 #include<string>
4 #include<queue>
5 using namespace std;
6 int main()
7 {
8 int cas,n,a,q,ok;
9 string s;
10 scanf("%d",&cas);
11 while(cas--)
12 {
13 priority_queue<int> small;//声明放在while里面
14 priority_queue<int,vector<int>,greater<int> > big;
15 scanf("%d",&n);
16 for(int i=1;i<=n/2;i++)
17 {
18 scanf("%d",&a);
19 small.push(a);
20 }
21 for(int i=n/2+1;i<=n;i++)
22 {
23 scanf("%d",&a);
24 big.push(a);
25 }
26 scanf("%d",&q);
27 while(q--)
28 {
29 cin>>s;
30 if(s=="drop")
31 {
32 scanf("%d",&a);
33 if(a<small.top())
34 {
35 if(small.size()==big.size())
36 {
37 big.push(small.top());
38 small.pop();
39 small.push(a);
40 }
41 else small.push(a);
42 }
43 else if(a>big.top())
44 {
45 if(small.size()==big.size())
46 big.push(a);
47 else
48 {
49 small.push(big.top());
50 big.pop();
51 big.push(a);
52 }
53 }
54 else
55 {
56 if(small.size()==big.size())
57 big.push(a);
58 else small.push(a);
59 }
60
61 }
62 else
63 {
64 if(small.size()==big.size())printf("%d %d\n",small.top(),big.top());
65 else printf("%d\n",big.top());
66 }
67 }
68
69 }
70 }