数据流的中位数：ACM 模式刷题

按标准输入读取测试数据，输出结果后可在 CodeACM 在线运行和提交。

题目描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

· 例如 arr = [2,3,4] 的中位数是 3 。

· 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

· MedianFinder() 初始化 MedianFinder 对象。

· void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

· double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10⁻⁵ 以内的答案将被接受。

输入格式

第一行输入操作数 q，接下来 q 行输入 addNum x 或 findMedian。保证查询时至少已有一个数。

输出格式

每个 findMedian 输出一行结果，保留一位小数。

数据范围

• 1 ≤ q ≤ 10⁵
• −10⁵ ≤ x ≤ 10⁵

公开样例

5
addNum 1
addNum 2
findMedian
addNum 3
findMedian

1.5
2.0

3
addNum -1
findMedian
addNum -2

-1.0

练习建议

先根据输入输出格式写出可运行程序，再用公开样例检查结果；遇到边界情况时，补充自测用例后提交。