算法題：去除極值後求平均值（The Average）C++ 解法

問題描述

給定 n 個正整數，去除最大的 n1 個和最小的 n2 個，計算剩餘數的平均值，保留 6 位小數。多測試用例，n ≤ 5,000,000，需 O(n log k) 算法。

核心思路：雙優先隊列（堆）

• 維護一個小頂堆保存最大的 n1 個數（堆頂為這組中最小值）
• 維護一個大頂堆保存最小的 n2 個數（堆頂為這組中最大值）
• 遍歷所有數，動態更新兩堆，累加總和
• 最後用總和減去兩堆元素和，除以剩餘個數

C++ 完整代碼

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n1, n2, n;
    while (cin >> n1 >> n2 >> n) {
        if (n1 == 0 && n2 == 0 && n == 0) break;
        
        // 小頂堆：保存最大的 n1 個
        priority_queue<long long, vector<long long>, greater<>> maxHeap;
        // 大頂堆：保存最小的 n2 個
        priority_queue<long long> minHeap;
        
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            long long x; cin >> x;
            sum += x;
            
            // 更新最大的 n1 個
            if ((int)maxHeap.size() < n1) {
                maxHeap.push(x);
            } else if (n1 > 0 && x > maxHeap.top()) {
                maxHeap.pop();
                maxHeap.push(x);
            }
            
            // 更新最小的 n2 個
            if ((int)minHeap.size() < n2) {
                minHeap.push(x);
            } else if (n2 > 0 && x < minHeap.top()) {
                minHeap.pop();
                minHeap.push(x);
            }
        }
        
        long long removed = 0;
        while (!maxHeap.empty()) { removed += maxHeap.top(); maxHeap.pop(); }
        while (!minHeap.empty()) { removed += minHeap.top(); minHeap.pop(); }
        
        double avg = (sum - removed) * 1.0 / (n - n1 - n2);
        cout << fixed << setprecision(6) << avg << "\n";
    }
    return 0;
}

關鍵點解析

• 空間優化：只存 n1+n2 個元素，而非全部 n（可達 500 萬），內存從 ~40MB 降至 ~幾百 KB。
• 時間複雜度：每個元素最多兩次堆操作，O(n log(n1+n2))，滿足限制。
• 精度處理：用 long long 累加和，最終轉 double 除法，setprecision(6) 保證輸出格式。
• 邊界情況：n1=0 或 n2=0 時堆不操作，代碼中 n1>0 判斷保證安全。

測試樣例

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

Output:
3.500000
562.500000

總結

海量數據求去極值平均值，雙堆流式處理是標準解法。掌握 priority_queue 的比較器用法（greater<> 為小頂堆）是關鍵。