1167 奖学金
大约 2 分钟
1167 奖学金
【算法】 排序、结构体排序
【C++】 sort、结构体、cmp 比较函数
【难度】 入门
一、题目简述
某小学要发奖学金,评选规则:有 ()个学生,每人 3 门课成绩(语文、数学、英语)。
排序规则(优先级从高到低):
- 总分从高到低
- 总分相同,语文成绩从高到低
- 总分和语文都相同,学号小的在前
按排名输出前 5 名的学号和总分。
二、解题思路
2.1 三关键字排序
这也是一个多关键字排序问题,有三个关键字:
| 优先级 | 关键字 | 排序方向 |
|---|---|---|
| 1 | 总分(语文+数学+英语) | 降序 |
| 2 | 语文成绩 | 降序 |
| 3 | 学号 | 升序 |
2.2 结构体设计
struct Student {
int id; // 学号
int chinese; // 语文
int math; // 数学
int english; // 英语
int total; // 总分
};2.3 比较函数
bool cmp(Student a, Student b) {
if (a.total != b.total)
return a.total > b.total; // 总分降序
if (a.chinese != b.chinese)
return a.chinese > b.chinese; // 语文降序
return a.id < b.id; // 学号升序
}2.4 手动模拟样例
输入(学号 1~6):
| 学号 | 语文 | 数学 | 英语 | 总分 |
|---|---|---|---|---|
| 1 | 90 | 67 | 80 | 237 |
| 2 | 87 | 66 | 91 | 244 |
| 3 | 78 | 89 | 91 | 258 |
| 4 | 88 | 99 | 77 | 264 |
| 5 | 67 | 89 | 64 | 220 |
| 6 | 78 | 89 | 98 | 265 |
按规则排序后:
| 排名 | 学号 | 总分 | 语文 |
|---|---|---|---|
| 1 | 6 | 265 | 78 |
| 2 | 4 | 264 | 88 |
| 3 | 3 | 258 | 78 |
| 4 | 2 | 244 | 87 |
| 5 | 1 | 237 | 90 |
取前 5 名输出即可。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
struct Student {
int id, chinese, math, english, total;
};
bool cmp(Student a, Student b) {
if (a.total != b.total)
return a.total > b.total;
if (a.chinese != b.chinese)
return a.chinese > b.chinese;
return a.id < b.id;
}
int main() {
int n;
cin >> n;
Student a[305]; // n < 300
for (int i = 0; i < n; i++) {
a[i].id = i + 1; // 学号从 1 开始
cin >> a[i].chinese >> a[i].math >> a[i].english;
a[i].total = a[i].chinese + a[i].math + a[i].english;
}
sort(a, a + n, cmp);
for (int i = 0; i < 5; i++) {
cout << a[i].id << " " << a[i].total << endl;
}
return 0;
}注:题目保证 ,所以直接输出前 5 个没有问题。
四、复杂度分析
- 时间复杂度:,排序开销。,瞬间完成。
- 空间复杂度:,存储 个学生的结构体数组。
五、易错点
- 学号从 1 开始:读入数据时,第 行的学生学号为 ,即输入的第 1 行是学号 0+1=1。代码中
a[i].id = i + 1。 - 总分计算公式:
total = chinese + math + english,不要漏掉某一科。 - 只输出前 5 名:
for (int i = 0; i < 5; i++),不是输出全部 个。 - 语文优先级高于学号:总分相同时先比语文,语文还相同才比学号。别把顺序搞反。
