动态维护中位数的题目。

我们采用对顶堆做法，建立一个大根堆存储前半段序列（排序后），小根堆存储后半段序列，通过维护两个堆使得他们元素个数之差不大于1 ，这样这个序列的中位数就是大根堆的堆顶。

关于如何维护对顶堆：如果两个堆元素个数差大于1，我们就把大根堆的堆顶放到小根堆当中（或是把小根堆堆顶放到大根堆当中）直到两个堆“平衡”为止。

ps：当堆空时调用top会导致RE，所以调用top前务必保证堆中有元素。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <vector>
 7 using namespace std;
 8 vector<int> ans;
 9 priority_queue<int>minn;
10 priority_queue<int,vector<int>,greater<int> >maxx;
11 int T,n,id;
12 inline int read() {
13     int ret=0;
14     int op=1;
15     char c=getchar();
16     while(c<'0'||c>'9') {if(c=='-') op=-1; c=getchar();}
17     while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
18     return ret*op;
19 }
20 int main() {
21     cin>>T;
22     while(T--) {
23         cin>>id>>n;
24         while(maxx.size()) maxx.pop();
25         while(minn.size()) minn.pop();
26         ans.clear();
27         for(int i=1,x;i<=n;i++) {
28             cin>>x;
29             if(maxx.empty()) maxx.push(x);
30             else if(x>maxx.top()) maxx.push(x);
31             else minn.push(x);
32             while(maxx.size()<minn.size()) {
33                 maxx.push(minn.top());
34                 minn.pop();
35             } 
36             while(maxx.size()-minn.size()>1) {
37                 minn.push(maxx.top());
38                 maxx.pop();
39             }
40             if(i%2) ans.push_back(maxx.top());
41         }
42         printf("%d %d\n",id,n/2+1);
43 //        puts("OK");
44         for(int i=0;i<ans.size();i++) {
45             if(i&&i%10==0) puts("");
46             if(i%10) putchar(' ');
47             printf("%d",ans[i]);
48         }
49         puts("");
50     }
51     return 0;
52 }

AC Code