POJ 2833 The Average（優先隊列）

原題目網址：http://poj.org/problem?id=2833

本題中文翻譯：

描述

 在演講比賽中，當選手完成演講時，評委将對他的演出進行評分。 從業人員删除最高成績和最低成績，并計算其餘成績的平均值作為參賽者的最終成績。 這是一個簡單的問題，因為通常隻有幾名評委。

讓我們考慮一下上面問題的一般形式。 給定n個正整數，删除最大的n1和最小的n2，并計算其餘的平均值。

 輸入

 輸入由幾個測試用例組成。 每個測試用例由兩行組成。 第一行包含三個整數n1，n2和n（1≤n1，n2≤10，n1 + n2 <n≤5,000,000）由一個空格隔開。 第二行包含n個正整數ai（對于所有ai, 1≤i≤n，1≤ai≤10^8）由一個空格隔開。 最後一個測試用例後面跟着三個零。

 輸出

 對于每個測試用例，輸出小數點後的平均值，并将其四舍五入為六位數字。

 Sample Input

1 2 5

1 2 3 4 5

4 2 10

2121187 902 485 531 843 582 652 926 220 155

0 0 0

Sample Output

3.500000

562.500000

Hint

This problem has very large input data. scanf and printf are recommended for C++ I/O.(不要用cin或cout)

The memory limit might not allow you to store everything in the memory.

（本題無法讓你一次性輸入整個序列，空間不允許）

解題思路：

先輸入n1+n2個數，将這些數排序，分别将最小的n2個放到大根堆裡，将最大的n1個放到小根堆裡。

每讀入一個元素，如果目前元素比大根堆堆頂小，說明堆頂一定參與計算，則将堆頂彈出，将目前元素推進去；如果目前元素比小根堆堆頂大，說明堆頂一定參與計算，則将堆頂彈出，将目前元素推進去；（感性了解一下）

如果不符合上面兩項條件，則說明目前元素一定參與計算。

AC代碼：

1 #include<cstdio>
 2 #include<queue>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 priority_queue<int > a;//大根堆 
 8 priority_queue<int ,vector<int> ,greater<int> > a1;//小根堆 
 9 int n,n1,n2,k,ll[21];
10 long long ans;
11 double ans1;
12 
13 int main() {
14     while(scanf("%d%d%d", &n1, &n2, &n) == 3 && n1 && n2 && n) {
15         while (!a.empty()) a.pop();//初始化一定要記得 
16         while (!a1.empty()) a1.pop();//初始化一定要記得
17         ans = ans1 = 0;//初始化一定要記得
18         for(int i = 1;i <= n1 + n2; i++)
19             scanf("%d",&ll[i]);
20         sort(ll+1,ll+n1+n2+1);
21         for(int i = 1;i <= n2; i++)
22             a.push(ll[i]);
23         for(int i = n2 + 1;i <= n2 + n1; i++)
24             a1.push(ll[i]);
25         for(int i = n1+n2+1;i <= n; i++) {
26             scanf("%d",&k);
27             if(k >= a1.top()) {
28                     ans += a1.top();
29                     a1.pop();
30                     a1.push(k);
31                     continue;
32             }
33             if(k <= a.top()) {
34                     ans += a.top();
35                     a.pop();
36                     a.push(k);
37                     continue;
38             }
39             ans += k;
40         }
41         ans1 = ans;
42         printf("%.6f\n",ans1 / (n - n1 -n2));
43     }
44     return 0;
45 }      

轉載于:https://www.cnblogs.com/lipeiyi520/p/10776820.html