【timegate】
https://www.luogu.org/problem/P1168
【解题思路】
使用两个堆，大根堆维护较小的值，小根堆维护较大的值
即小根堆的堆顶是较大的数中最小的，大根堆的堆顶是较小的数中最大的
【code】
1 #include <cstdio>
2 #include <queue>
3 #include <cmath>
4 #include <iostream>
5 #include <algorithm>
6 using namespace std;
7 int n,a;
8 priority_queue<int> q;
9 priority_queue<int,vector<int>,greater<int> > qq;
10 int main(){
11 scanf("%d",&n);
12 scanf("%d",&a);
13 q.push(a);
14 printf("%d\n",a);
15 for(register int i=2;i<=n;i++){
16 scanf("%d",&a);
17 if (a>q.top())
18 qq.push(a);
19 else q.push(a);
20 while (q.size()-qq.size()>1){
21 if (q.size()>qq.size()){
22 qq.push(q.top());
23 q.pop();
24 }
25 else{
26 q.push(qq.top());
27 qq.pop();
28 }
29 }
30 if (i&1)
31 printf("%d\n",q.size()>qq.size()?q.top():qq.top());
32 }
33 return 0;
34 }