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;
}      

轉載于:https://www.cnblogs.com/tallisHe/p/4042083.html