【深基7.例4】歌唱比赛

解题思路

每名选手统计总分、最大分和最小分。用总分减去一个最大分和一个最小分，再除以 m-2。维护所有选手得分的最大值。

正确性说明

减法恰好剔除两名评委的评分，即使最高分或最低分重复，也只减去各一个。遍历维护最大值得到最高得分。

易错点

平均数使用实数除法；最高分、最低分各去掉一个，不能去掉所有相同分数。题意要求至少三名评委。

复杂度

时间 O(nm)，空间 O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    double best = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0, lo = 11, hi = -1;
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            sum += x;
            lo = min(lo, x);
            hi = max(hi, x);
        }
        best = max(best, 1.0 * (sum - lo - hi) / (m - 2));
    }
    cout << fixed << setprecision(2) << best << "\n";
    return 0;
}