题目链接：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;}
