首页 > 代码库 > poj 2833 The Average
poj 2833 The Average
题目链接：http://poj.org/problem?id=2833
思路：
由于数据量较大，超出存储范围，使用不能使用数组存储数据在进行排序。考虑维护一个最大堆与最小堆，依次读取数据，记录数据中的n1个最大数字与n2个最小数据，所有数据累计和减去堆中数据即可。
注：注意使用记录n2个最大数据要使用最小堆，因为每一个数据需要与该堆中最小值比较，同理，记录n1个最小数据要使用最大堆。
代码：
#include <iostream>#include <queue>using namespace std;struct cmp{ bool operator()( const int a, const int b ) { return a > b; }};priority_queue<int>MaxHeap;priority_queue<int, vector<int>, cmp >MinHeap;int main(){ int n1, n2, n; double Sum = 0, Ave; while ( scanf( "%d %d %d", &n1, &n2, &n ) != EOF ) { int Tmp, CountMin, CountMax; Sum = CountMin = CountMax = 0; if ( n1 == 0 && n2 == 0 && n == 0 ) break; for ( int i = 0; i < n; ++i ) { scanf( "%d", &Tmp ); Sum += Tmp; if ( CountMin < n1 ) { CountMin++; MinHeap.push( Tmp ); } else if ( Tmp > MinHeap.top() ) { MinHeap.pop(); MinHeap.push( Tmp ); } if ( CountMax < n2 ) { CountMax++; MaxHeap.push( Tmp ); } else if ( Tmp < MaxHeap.top() ) { MaxHeap.pop(); MaxHeap.push( Tmp ); } } while ( !MaxHeap.empty() ) { int Tmp = MaxHeap.top(); MaxHeap.pop(); Sum -= Tmp; } while ( !MinHeap.empty() ) { int Tmp = MinHeap.top(); MinHeap.pop(); Sum -= Tmp; } Ave = Sum / ( n - n1 - n2 ); printf( "%.6f\n", Ave ); } return 0;}
poj 2833 The Average
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。