题目原型为洛谷 P1093 [NOIP2007 普及组] 奖学金。本题考察的是结构体多关键字排序:排序的「主键」不是单一字段,而是一条比较优先级链。
目标
完成本题后,你应该能够:
- 把一个多字段的比较规则,写成一个逐层下钻的自定义比较器;
- 理解「决胜键」的作用:当所有主键都相同时,用学号这类唯一键保证排序结果稳定;
- 用
std::sort+ 自定义比较器解决多关键字排名问题。
前置知识
- 10.1 插入排序、10.2 选择排序、10.3 冒泡排序中「比较器」的概念;
std::sort的用法与自定义cmp函数。
题目
某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。学期末每个学生都有语文、数学、英语三门课的成绩。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学排在前面。
输入格式
- 第一行一个整数
n,表示学生人数; - 接下来
n行,每行三个整数,依次表示第i名学生的语文、数学、英语成绩(1 ≤ i ≤ n)。
输出格式
输出前 5 名学生的学号和总分,共 5 行;如果不足 5 人,则按实际人数输出。
数据范围
| 项目 | 范围 |
|---|---|
学生人数 n | 1 ≤ n ≤ 300 |
| 三科成绩 | 0 ≤ 成绩 ≤ 100 |
| 输出人数 | min(5, n) |
样例
样例输入
input
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98样例输出
output
6 265
4 264
3 258
2 244
1 237样例解释
六名学生的总分依次为:237、244、258、264、220、265。按总分降序,前 5 名依次是学号 6(265)、4(264)、3(258)、2(244)、1(237)。学号 5 总分 220 排第 6,不在前 5 名。
如何验证
先安装 Node.js、pnpm 和支持 C++17 的编译器。
powershell
# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make scoreWindows 没有安装 Make 时,在仓库根目录使用等价的 pnpm 入口:
powershell
pnpm lab:run -- labs/chapter-10/exercise/E-10-01-multi-key-sort
pnpm lab:score -- labs/chapter-10/exercise/E-10-01-multi-key-sort标准输出参与判题,调试信息请写入标准错误。
完成清单
思考题
- 如果去掉比较器里的第三条「学号升序」,用
std::sort排序后,总分和语文都相同的同学的相对顺序还稳定吗?为什么? - 为什么这里要用「学号」这个唯一键兜底?如果学号也可能重复,还能保证排名唯一吗?