P4680 奖学金问题（基础）

解题思路

第一步，把信息打包。 每个同学有学号 id 和总分 total 两个信息，用结构体 Student 装在一起，就像一张小卡片，排序时可以整张一起移动。开数组 students 存学生，学号从 1 开始。读入三门课成绩 chinese、math、english 后，用 chinese + math + english 算出总分 total。

第二步，定排序规则。 题目要求"先按总分从高到低，如果总分相同，学号小的排前面"，这就是双关键字排序。写比较函数 cmp：总分不同，总分大的排前面；总分相同，学号小的排前面。sort 会照着我们定的规矩排好队。

第三步，排序。 因为学号从 1 开始存，排序区间要写成 sort(students + 1, students + n + 1, cmp)，这是"左闭右开"的写法。排完后数组第 1 到第 5 个元素就是前五名。

第四步，输出。 循环输出前五名同学的学号和总分，每行一个。

用样例验证。 六名同学的总分依次是 237、244、258、264、220、265，排好序后第一名是 6 号（265 分）、第二名是 4 号（264 分）、第三名是 3 号（258 分）、第四名是 2 号（244 分）、第五名是 1 号（237 分），和样例输出完全一致。

边界情况： 题目保证至少有五名同学参加评选，循环输出前五名不会越界；n 最大 100，数组开 105 足够；注意 sort 的区间写法是从 students+1 到 students+n+1。

参考代码

// P4680 奖学金问题：计算每名学生三门课的总分，按总分从高到低排序，总分相同学号小的在前，输出前五名学号和总分
#include <iostream>
#include <algorithm>
using namespace std;

struct Student {
    int id;
    int total;
};

bool cmp(Student x, Student y) {
    if (x.total != y.total) return x.total > y.total; // 总分高的排前面
    return x.id < y.id; // 总分相同，学号小的排前面
}

int main() {
    int n;
    cin >> n;
    Student students[105];
    for (int i = 1; i <= n; i++) {
        int chinese, math, english;
        cin >> chinese >> math >> english;
        students[i].id = i;
        students[i].total = chinese + math + english; // 计算总分
    }
    sort(students + 1, students + n + 1, cmp); // 从第一名开始排序
    for (int i = 1; i <= 5; i++) {
        cout << students[i].id << " " << students[i].total << endl;
    }
    return 0;
}

复杂度分析

排序用到 sort()，它内部是快速排序，对 n 个元素排序的时间是 O(n log n)。这里 n≤100，log n 很小，速度飞快。读入成绩并计算总分是一趟 O(n) 的循环，最后输出前五名是常数时间。总时间复杂度 O(n log n)。空间上只用一个长度 105 的结构体数组存放学生信息，空间复杂度 O(n)。