大数据排序

The Average
输入：几个测试用例组成。 每个测试用例由两行组成。 第一行包含三个整数 n_1, _n_2 and _n (1 ≤ n_1, _n_2 ≤ 10, _n_1 + _n_2 < _n ≤ 5,000,000) ，每两个数之间由一个空格分隔。 第二行包含 n 个正整数 ai (1 ≤ ai ≤ 108 i (1 ≤ i ≤ n) ）由单个空格分隔。 最后一个测试用例后跟三个零。
输出：对于每个测试用例，在单独的一行中输出四舍五入到小数点后六位的平均值。

思路：优先队列

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 5000010;
int n, up, down;
int main() {
    while (scanf("%d%d%d", &up, &down, &n), n) {
        double s = 0;
        priority_queue<int> r;
        priority_queue<int, vector<int>, greater<int>> l;
        int x;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            s += x;
          // 小小的优化 
            if (r.size() < down) {
                r.push(x);
            } else if (x < r.top()) {
                r.pop();
                r.push(x);
            }
            if (l.size() < up) {
                l.push(x);
            } else if (x > l.top()) {
                l.pop();
                l.push(x);
            }
        }
        while (!l.empty()) {
            x = l.top();
            l.pop();
            s -= x;
        }
        while (!r.empty()) {
            x = r.top();
            r.pop();
            s -= x;
        }
        printf("%.6lf\n", s / (n - up - down));
    }
    return 0;
}