杭電 ACM 4520 題解：小Q系列——最佳裁判 (貪心 + 排序 + 多重集)

題目大意 (重構)

小 Q 擔任裁判，需對選手得分進行處理，去除最高最低分後求平均，或類似的「去極值統計」問題。核心是貪心策略 + 高效數據結構維護有序序列。

核心算法

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; // n 選手, m 裁判
    while (cin >> n >> m) {
        vector> scores(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int x; cin >> x;
                scores[i].insert(x);
            }
        }

        for (int i = 0; i < n; i++) {
            auto& ms = scores[i];
            // 去除最高最低
            ms.erase(ms.begin());       // 最低
            ms.erase(prev(ms.end()));   // 最高

            // 計算平均
            long long sum = 0;
            for (int v : ms) sum += v;
            double avg = (double)sum / ms.size();
            cout << fixed << setprecision(2) << avg << "\n";
        }
    }
    return 0;
}

關鍵點解析

1. multiset 自動有序：紅黑樹實現，插入/刪除/查找 O(log m)，自動處理重複分數。
2. 去極值：begin() 最小，prev(end()) 最大。erase(iterator) 只刪一個元素 (關鍵！erase(value) 會刪所有相等值)。
3. 精度控制：用 long long 累加避免溢出，double 除法，setprecision(2) 保留兩位小數。
4. 多測試用例：while (cin >> n >> m) 讀到 EOF 結束。

優化：前綴和數組 (若 m 固定、多次查詢)

// 若每個選手分數固定，預排序存 vector，前綴和 O(1) 區間求和
vector> a(n, vector(m));
for (auto& v : a) { sort(v.begin(), v.end()); }
vector> pref(n, vector(m+1));
for (int i=0;i