P4664 数据统计（提高）

解题思路

第一步，读懂题目。 有 n 名同学，每人有姓名和语文、数学、英语三科成绩。要算出平均分，评出等级（平均分大于 95 是 excellent，60~95 之间是 good，小于等于 60 是 bad），然后按平均分从高到低输出前 m 名；如果平均分相同，先输入的排在前面。

第二步，想想生活里的例子。 老师在排"学习之星"名单，先按平均分排队，平均分一样高的同学就按报名顺序站，不能乱了次序。比如小明和小红的平均分一样都是 90 分，小明先输入，就还是小明排在前面。

第三步，用结构体打包数据。 用结构体 Student 把姓名、三科成绩、平均分打包在一起。平均分用 (chinese+math+english)/3.0 计算，注意要除以 3.0 而不是 3，这样才是小数，不然会丢掉小数部分。

第四步，用归并排序按平均分降序排。 题目要求用归并排序。合并时如果左边平均分 >= 右边，就把左边放进临时数组，这样平均分相等时左边的（先输入的）会先出来，天然保持输入顺序。

第五步，输出前 m 名。 排完后取前 m 个，按等级规则判断并保留两位小数输出。注意 m 是在 n 个学生之后才输入的，要读完全部学生再读 m，这个顺序不能错。

第六步，注意边界细节。 平均分恰好 60 分算 bad，恰好 95 分算 good，判断时注意等于号；保留两位小数用 printf 的 %.2f。n 最大接近 100000，数组开 100005 才够。另外平均分是用 double 存的小数，和整数 60、95 比较时直接用大于、大于等于就行，不用担心精度问题。

参考代码

// P4664 数据统计：结构体存姓名和三科成绩，归并排序按平均分降序，并列保持输入顺序
#include <iostream>
#include <cstdio>

struct Student {
    char name[50];
    int chinese, math, english;
    double average;
};

Student students[100005], temp[100005];

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (students[i].average >= students[j].average) temp[k++] = students[i++];   // >= 保证并列时先取左边，保持输入顺序
        else temp[k++] = students[j++];
    }
    while (i <= mid) temp[k++] = students[i++];
    while (j <= r) temp[k++] = students[j++];
    for (int p = l; p <= r; p++) students[p] = temp[p];
}

int main() {
    int n, m;
    std::scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        std::scanf("%s%d%d%d", students[i].name, &students[i].chinese, &students[i].math, &students[i].english);
        students[i].average = (students[i].chinese + students[i].math + students[i].english) / 3.0;   // 平均分
    }
    std::scanf("%d", &m);
    mergeSort(0, n - 1);
    for (int i = 0; i < m; i++) {
        const char* level = "bad";
        if (students[i].average > 95) level = "excellent";
        else if (students[i].average >= 60) level = "good";
        std::printf("%s %s %.2f\n", students[i].name, level, students[i].average);
    }
    return 0;
}

复杂度分析

归并排序时间复杂度 O(n log n)，n 最大接近 100000，约 170 万次比较，很快。归并排序是稳定排序，正好满足"平均分相同按输入顺序"的要求。空间上需要一个结构体数组 students 和一个临时数组 temp，约 12MB，在限制内。输出 m 个同学是 O(m)。这道题把"结构体 + 稳定排序 + 保留小数"三个知识点串在一起，很值得练习。