題目鏈接：http://algorithm.openjudge.cn/betaexam/C/ 總時間限制: 3000ms 內存限制: 65536kB
描述
設計一個數據結構，初始為空，支持以下操作：
（1）增加一個元素，要求在log(n)時間內完成，其中n是該數據結構中當前元素的個數。注意：數據結構中允許有重復的元素。
（2）返回當前元素集合的中位數，要求在常數時間內完成。如果當前元素的個數為偶數，那么返回下中位數（即兩個中位數中較小的一個）。
（3）刪除中位數，要求在log(n)時間內完成。
輸入
輸入的第一行是一個自然數T，代表測試數據的組數((1 ≤ T ≤ 600))。每組測試數據的第一行是個自然數N，代表操作的次數，1<=N<=10000。后面的N行中的每行代表一個操作，每次操作首先輸入一個單字符代表操作的類型：
I表示插入，后面跟著輸入一個正整數（這是唯一帶有輸入數值的操作）。 Q表示查詢，輸出當前的中位數（這是唯一產生輸出的操作）。 D表示刪除當前的中位數。
輸入保證是正確的：查詢時集合保證不為空（即中位數是存在的），刪除時保證集合中有足夠可供刪除的元素。
輸出
每次查詢操作Q時輸出的中位數，每次輸出單獨占一行。
樣例輸入
1 8 I 4 I 3 I 5 Q D I 10 I 2 Q
樣例輸出
4 3
提示
123
來源
課程
解題思路
題目要求插入和刪除的時間復雜度都是log(n)，說明必須要用樹型數據結構了，考慮到每次只需要維護中位數，感覺上使用堆會比較合適。但是堆只能維護最大值或最小值，怎么用堆來維護中位數呢？答案是用兩個堆，一個最大堆，一個最小堆，每次插入或刪除元素的時候對兩個堆進行調整，使得他們保持平衡狀態，這樣中位數就會在這兩個堆頂元素里了。
AC代碼
#include<bits/stdc++.h>using namespace std;int n,t;PRiority_queue<int> lq;priority_queue<int,vector<int>,greater<int> > rq;void push_num(int x){ if(lq.empty()){ lq.push(x); } else{ if(x>=lq.top()){ rq.push(x); } else{ lq.push(x); } } int tmp; while(lq.size()-1>rq.size()){ tmp=lq.top(); lq.pop(); rq.push(tmp); } while(lq.size()<rq.size()){ tmp=rq.top(); rq.pop(); lq.push(tmp); }}void showmid(){ printf("%d/n",lq.top());}void delmid(){ lq.pop(); int tmp; while(lq.size()>rq.size()+1){ tmp=lq.top(); lq.pop(); rq.push(tmp); } while(lq.size()<rq.size()){ tmp=rq.top(); rq.pop(); lq.push(tmp); }}int main(){ int a; char c; scanf("%d",&t); while(t--){ while(!lq.empty()) lq.pop(); while(!rq.empty()) rq.pop(); scanf("%d",&n); while(n--){ scanf("%c",&c); scanf("%c",&c); if(c=='I'){ scanf("%d",&a); push_num(a); } else if(c=='Q'){ showmid(); } else{ delmid(); } } } return 0;}
