C++ 歌唱比赛评分算法：求最高得分

问题描述：

n(n≤100) 名同学参加歌唱比赛，并接受 m(m≤20) 名评委的评分，评分范围是 0 到 10 分。这名同学的得分就是这些评委给分中去掉一个最高分，去掉一个最低分，剩下 m−2 个评分的平均数。请问得分最高的同学分数是多少？评分保留 2 位小数。

输入格式：

第一行两个整数 n,m。接下来 n 行，每行各 m 个整数，表示得分。

输出格式：

输出分数最高的同学的分数，保留两位小数。

输入输出样例：

输入 #1

7 6 4 7 2 6 10 7 0 5 0 10 3 10 2 6 8 4 3 6 6 3 6 7 5 8 5 9 3 3 8 1 5 9 9 3 2 0 5 8 0 4 1 10

输出 #1

6.00

C++ 代码：

#include <iostream>
#include <iomanip>

using namespace std;

int sum(int nums[], int length) {
    int s = 0;
    for (int i = 0; i < length; i++) s += nums[i];
    return s;
}

int max(int nums[], int length) {
    int m = nums[0];
    for (int i = 1; i < length; i++)
        if (nums[i] > m)
            m = nums[i];
    return m;
}

double maxDouble(double nums[], int length) {
    double m = nums[0];
    for (int i = 1; i < length; i++)
        if (nums[i] > m)
            m = nums[i];
    return m;
}

int min(int nums[], int length) {
    int m = nums[0];
    for (int i = 1; i < length; i++)
        if (nums[i] < m)
            m = nums[i];
    return m;
}

double average(int nums[], int length) {
    return (double(sum(nums, length)) - max(nums, length) - min(nums, length)) / (length - 2);
}

int main() {
    int n, m;
    cin >> n >> m;
    double averages[n];
    int nums[m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> nums[j];
        }
        averages[i] = average(nums, m);
    }
    printf("%.2f", maxDouble(averages, n));
    return 0;
}

算法分析：

暴力枚举：$O(nm^2)$
- 遍历所有同学的评分，对于每个同学，计算去掉最高分和最低分后的平均分。
- 比较所有同学的平均分，找出最高分。

改进：

代码中 maxDouble(averages, m) 函数的第二个参数应为 n，因为 averages 数组存储的是所有同学的平均分，长度为 n。

时间复杂度：

算法的时间复杂度为 $O(nm^2)$，因为需要遍历所有同学的评分，并计算每个同学的平均分。

参考文献：

其他优化思路：

可以使用排序算法将每个同学的评分排序，然后直接取中间的 m-2 个分数进行计算，避免重复计算最大值和最小值。
可以使用优先队列或者堆来维护每个同学的评分，方便快速找到最大值和最小值。