Source:
POJ 2833 The AverageProblem Description：
一组数据，去掉最大和最小的几个数，然后求剩下的数的平均值。Hint:
由于输入数据比较大，故采用 scanf 和 printf. 由于内存有限制，所以不可能保存每一个数。直接存储会超内存。因为n1,n2都很小，用大根堆和小根堆分别存储 最小的n2个数 和最大的n1个数。 然后用总的平均值减去这些数分别除以输入数的总个数即可。Code:
#include<iostream>#include<fstream>#include<vector>#include<string>#include<queue>#include<iterator>#include<algorithm>#include<functional>#include<iomanip>#include<numeric>using namespace std;int main(){#ifdef ONLINE_JUDGE#elsefreopen("D:\\in.txt", "r", stdin);freopen("D:\\out.txt", "w", stdout);#endifint n(0), n1(0), n2(0);int a(0);double avg(0);while (scanf("%d%d%d",&n1, &n2,&n) && !(0 == n && 0 == n1 && 0 == n2)){priority_queue<int, vector<int>, greater<int> > spq;//小根堆priority_queue<int> bpq;//大根堆avg = 0;unsigned int size = n - n1 - n2;for (int i = 0; i < n;i++){scanf("%d", &a);avg += a*1.0 / size;//由于大根堆每次pop当前堆中最大的元素，所以用大根堆保存要删除的最小的几个数if (bpq.size() < n2){bpq.push(a);}else {if (a < bpq.top()){bpq.pop();bpq.push(a);}}//由于小根堆每次pop当前堆中最小的元素，所以用小根堆保存要删除的最大的几个数if (spq.size() < n1){spq.push(a);}else{if (a>spq.top()){spq.pop();spq.push(a);}}}while (!spq.empty()){avg -= spq.top()*1.0 / size;spq.pop();}while (!bpq.empty()){avg -= bpq.top()*1.0 / size;bpq.pop();}printf("%.6lf\n", avg);}return 0;}
附：Priority_queue的简单介绍
对于自定义类型，则必须自己重载 operator< 或者自己写仿函数:
#include <iostream>#include <queue>using namespace std;struct Node{int x, y;}node;bool operator<( Node a, Node b){if(a.x==b.x) return a.y>b.y;return a.x>b.x;}int main(){priority_queue<Node>q;for(int i=0;i<10;i++){node.x=i;node.y=10-i/2;q.push(node);}while(!q.empty()){cout<<q.top().x <<' '<<q.top().y<<endl;q.pop();}return 0;}
自定义类型重载 operator< 后，声明对象时就可以只带一个模板参数。
此时不能像基本类型这样声明priority_queue<Node, vector<Node>, greater<Node> >;
原因是 greater<Node> 没有定义，如果想用这种方法定义
则可以按如下方式
例子:（ 个人喜欢这种方法，因为set的自定义比较函数也可以写成这种形式）
#include <iostream>#include <queue>using namespace std;struct Node{int x, y;}node;struct cmp{bool operator()(Node a,Node b){if(a.x==b.x) return a.y>b.y;return a.x>b.x;}};int main(){priority_queue<Node,vector<Node>,cmp>q;for(int i=0;i<10;i++){node.x=i;node.y=10-i/2;q.push(node);}while(!q.empty()){cout<<q.top().x<<' '<<q.top().y<<endl;q.pop();}return 0;}
