下载掌阅APP，畅读海量书库
立即打开
题目描述（POJ2833）： 在演讲比赛中，评委对参赛者的表演进行评分。评分方法：给定 n 个正整数评分，删除最大的 n 1 个和最小的 n 2 个评分，将其余评分的平均值作为参赛者的最终成绩。请给出参赛者的最终成绩。
输入： 输入包含几个测试用例，每个测试用例都包含两行：第1行包含3个整数 n 1 、 n 2 和 n （1≤ n 1 , n 2 ≤10， n 1 + n 2 < n ≤5×10 6 ）；第2行包含 n 个正整数 a i （1≤ a i ≤10 8 ，1≤ i ≤ n ）。在最后一个测试用例后跟3个0。
输出： 对每个测试用例，都单行输出参赛者的最终成绩，保留小数点后6位。
提示： 此问题的输入数据非常大。对C++I/O，建议使用scanf和printf。内存限制可能不允许将所有内容都存储在内存中。
题解： 本题数据量很大，不要存储所有数据，只需用两个队列分别存储最大的 n 1 个数和最小的 n 2 个数即可。
定义两个优先队列， q 1 最大值优先，存储最小的 n 2 个数； q 2 最小值优先，存储最大的 n 1 个数。用总和减去这两个优先队列的元素值，然后求平均数。
