P4612 奖学金2（基础）

解题思路

这道题就像班级里评选奖学金，规则一条接一条，可以分四步来做。

第一步，把排序规则弄清楚。 先比总分，总分高的排前面；总分一样再比语文，语文高的排前面；总分和语文都一样，最后比学号，学号小的排前面。三条规则像比赛一样一层层比下去，第一项分不出胜负才比第二项。

第二步，用结构体把每个同学的信息装好。 每个同学要记住学号、语文成绩和总分，所以定义一个结构体 Student。数学和英语只用来算总分，排序用不到，就不必存进结构体。读入时顺便把总分算好，学号按输入顺序从 1 开始编号。

第三步，用 sort() 和比较函数排序。 sort() 可以给整个数组排序，但我们得告诉它按什么顺序排，这就要自己写一个比较函数。比较函数里用 if 一层层判断：先看总分是否相同，不同就按总分从大到小；总分相同再看语文；还相同就比学号。这样 sort() 就能按题目要求把同学排好。以样例为例，第 8 个同学语文 78、数学 89、英语 98，总分 265 全场最高，稳稳排在第一名。

第四步，输出前五名并防越界。 输出前五名的学号和总分，注意循环条件写成 i < 5 && i < n：如果总人数不足 5 人，就只输出实际的人数，避免数组越界。每行两个数，中间用空格隔开。

**回顾总结。**这道题的套路是：把比较规则想清楚，一层层写进比较函数，其余交给 sort() 完成。先比总分、再比语文、最后比学号，任何两名同学都能分出先后。以后遇到"按多条规则排序"的题目，都可以照这个模式：把每条规则按优先级排好，一项项比下去。

参考代码

// 奖学金2：按总分降序、语文降序、学号升序排序，输出前5名
#include <iostream>
#include <algorithm>
using namespace std;

// 保存一名学生的信息
struct Student {
    int id;           // 学号（按输入顺序 1~n）
    int chinese;      // 语文成绩
    int score;        // 三门总分
};

// 自定义比较函数：先比总分，再比语文，最后比学号
bool cmp(const Student &a, const Student &b) {
    if (a.score != b.score) return a.score > b.score;       // 总分高的靠前
    if (a.chinese != b.chinese) return a.chinese > b.chinese;   // 语文高的靠前
    return a.id < b.id;                                       // 学号小的靠前
}

int main() {
    int n;
    Student students[305];
    cin >> n;
    for (int i = 0; i < n; i++) {
        int math, english;
        cin >> students[i].chinese >> math >> english;
        students[i].id = i + 1;
        students[i].score = students[i].chinese + math + english;   // 计算总分
    }
    sort(students, students + n, cmp);   // 按规则排序
    for (int i = 0; i < 5 && i < n; i++) {         // 输出前 5 名
        cout << students[i].id << ' ' << students[i].score << endl;
    }
    return 0;
}

复杂度分析

sort() 排序的时间复杂度是 O(n log n)，n 是学生人数，题目保证 n ≤ 300，排序非常快。结构体数组占用的空间是 O(n)。输出只取前五名，不影响复杂度。整个程序在时间限制内可以轻松完成。