1166 成绩排序
大约 2 分钟
1166 成绩排序
【算法】 排序、结构体排序
【C++】 sort、结构体、cmp 比较函数、string
【难度】 入门
一、题目简述
给定 ()个学生的名字和成绩,按成绩从高到低排序输出。如果有相同分数,名字字典序小的在前。
名字只包含字母,长度不超过 20;成绩为非负整数且不超过 100。
二、解题思路
2.1 问题分析
这是一个双关键字排序问题:
- 第一关键字:成绩,降序(从高到低)
- 第二关键字:名字,升序(字典序小的在前)
数据范围 极小,任何排序方法都能过。推荐用 sort + 自定义 cmp 函数。
2.2 结构体设计
struct Student {
string name;
int score;
};2.3 比较函数
bool cmp(Student a, Student b) {
if (a.score != b.score)
return a.score > b.score; // 成绩高的在前
return a.name < b.name; // 名字字典序小的在前
}2.4 手动模拟样例
输入:
4
Kitty 80
Hanmeimei 90
Joey 92
Tim 28排序过程:
| 名字 | 成绩 | 排序规则 |
|---|---|---|
| Joey | 92 | 最高分,排第 1 |
| Hanmeimei | 90 | 第二高分,排第 2 |
| Kitty | 80 | 第三高分,排第 3 |
| Tim | 28 | 最低分,排第 4 |
输出:
Joey 92
Hanmeimei 90
Kitty 80
Tim 28三、参考代码
#include <bits/stdc++.h>
using namespace std;
struct Student {
string name;
int score;
};
bool cmp(Student a, Student b) {
if (a.score != b.score)
return a.score > b.score; // 成绩降序
return a.name < b.name; // 名字升序
}
int main() {
int n;
cin >> n;
Student a[25]; // n < 20,开 25 足够
for (int i = 0; i < n; i++) {
cin >> a[i].name >> a[i].score;
}
sort(a, a + n, cmp);
for (int i = 0; i < n; i++) {
cout << a[i].name << " " << a[i].score << endl;
}
return 0;
}四、复杂度分析
- 时间复杂度:,
sort的复杂度。,瞬间完成。 - 空间复杂度:,存储 个学生的数组。
五、知识扩展
5.1 字典序
字符串的字典序就是我们在字典中查单词的顺序。比较规则:从左到右逐个字符比较,遇到不同字符时,ASCII 码小的字符所在的字符串较小。比如 "Kitty" < "Tim",因为 'K' 的 ASCII 码(75)小于 'T'(84)。
C++ 的 string 直接支持 <, > 等比较运算符,无需手写。
5.2 成绩相同时的处理
本题明确要求"名字字典序小的在前",如果去掉这个条件(任意顺序均可),可以简化 cmp 为:
bool cmp(Student a, Student b) {
return a.score > b.score;
}但不保证成绩相同时的顺序。如果题目要求"稳定排序"(相同成绩保持输入顺序),则应该用 stable_sort。
