题目链接:https://cn.vjudge.net/problem/POJ-2833
题意:
在一组打分中,去掉 n1 个最高分,去掉 n2 个最低分,然后用剩下的分数计算选手得分。
分析:
这道题看起来可以直接把所有的分数存起来,排序一下之后把中间的加起来求平均,但实际上这道题因为数据量太大,这样做就超时了。看题目我们发现 n1 和 n2 两个数据都不超过 10,所以我们可以在输入数据时将所有分数加起来,然后同时维护一个最大优先队列和一个最小优先队列,每个里面都只存需要去掉的最大和最小值,最后将两个优先队列中的数据减去就行。需要注意的是,printf 无论是 %f 还是 %lf 没有区别,因为当 printf 函数当遇到 float 类型时会自动转化为 double,从 C 语言标准来说 printf 并没有 %lf 的定义,虽然大多数编译器都能接受,但在做题时 printf 最好用 %f,否则可能出现一些莫名其妙的错误。
代码:
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
int n1, n2, n, x;
while(scanf("%d %d %d", &n1, &n2, &n) && n != 0){
priority_queue< int, vector<int>, less<int> > qsmall; //最小优先队列
priority_queue< int, vector<int>, greater<int> > qbig; //最大优先队列
double sum = 0.0;
for(int i = 0; i < n; i++){
scanf("%d", &x);
sum += x;
qsmall.push(x);
qbig.push(x);
if(qsmall.size() > n2){
qsmall.pop();
}
if(qbig.size() > n1){
qbig.pop();
}
}
for(int i = 0; i < n1; i++){
sum -= qbig.top();
qbig.pop();
}
for(int i = 0; i < n2; i++){
sum -= qsmall.top();
qsmall.pop();
}
printf("%.6f\n", sum / (n - n1 - n2));
}
return 0;
}