OpenJudge

C:Dynamic Median

总时间限制:
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
来源
课程

1. STL编程接口:
1)(多道题均可能用到)STL队列中queue.push()是在“队尾”插入,“队头”元素访问用queue.front(),并需要额外调用queue.pop()来删除“队头”元素
2)(dynamic median)STL中声明一个int元素的优先队列(缺省为最大堆)的方法:priority_queue<int> pq; 如果需要最小堆:priority_queue<int, vector<int>, greater<int> > pq; greater<int> 所在的头文件为<functional>
2. 输入输出格式:
(heavy transportation) 题意要求每个case结束之后单独输出一个空行,而样例并未体现这一点
3. 其他需要注意的地方:
(dynamic median/股票买卖)输入数据量较大,应使用scanf而不是cin,否则有可能超时
(polygon)注意 -1 % n (n为正整数) 仍为 -1

其他问题可以到提问板上提问或者直接找助教

全局题号
8885
提交次数
829
尝试人数
126
通过人数
120