下载掌阅APP，畅读海量书库
立即打开
题目描述（HDU4006）： 小明和小宝正在玩数字游戏。游戏有 n 轮，小明在每轮中都可以写一个数，或者问小宝第 k 大的数是什么（第 k 大的数指有 k -1个数比它大）。游戏格式为：I c ，表示小明写下一个数 c ；Q，表示小明问第 k 大的数。请对小明的每个询问都给出第 k 大的数。
输入： 输入包含多个测试用例。每个测试用例的第1行都包含两个正整数 n 、 k （1≤ k ≤ n ≤1000000），表示 n 轮游戏和第 k 大的数。然后是 n 行，格式为I c 或Q。
输出： 对每个询问Q，都单行输出第 k 大的数。
提示： 当写下的数字个数小于 k 个时，小明不会问小宝第 k 大的数。
题解： 本题数据范围很大，直接暴力肯定超时，因此可以借助优先队列实现。
（1）使用优先队列（最小值优先）存储最大的 k 个数。
（2）插入。若队中元素个数小于 k ，则直接入队；若当前输入元素大于队头，则队头出队，当前元素入队。
（3）查询。队头（堆顶）就是第 k 大的数，输出即可。
根据输入样例，操作过程如下。
（1）插入。I 1：元素个数小于3，直接入队。I 2：元素个数小于3，直接入队。I 3：元素个数小于3，直接入队。
（2）查询。查询第3大的数，队头1为第3大的数。数字3是第1大。
（3）插入。I 5：元素个数不小于3，5比队头大，则队头出队，5入队。
（4）查询。查询第3大的数，队头2为第3大的数。
（5）插入。I 4：元素个数不小于3，4比队头大，则队头出队，4入队。
（6）查询。查询第3大的数，队头3为第3大的数。
