#MYD2. 成绩排名
成绩排名
题目描述
班里有 n 名同学参加了考试。给出每位同学的姓名(不含空格的字符串)与分数。请你按分数从高到低输出姓名;分数相同的同学按输入给出的先后顺序输出(即稳定排序)。
输入格式
第一行一个整数 n。接下来 n 行,每行一个不含空格的字符串 name_i(≤ 20 个字符)和一个整数 score_i。
输出格式
共 n 行,按分数从高到低、同分按输入顺序输出姓名。
数据范围
1 ≤ n ≤ 10000,0 ≤ score_i ≤ 100。姓名互不相同。
样例
4
Alice 90
Bob 85
Carol 90
Dave 70
Alice
Carol
Bob
Dave
说明/提示
考察稳定排序的使用。
解析
思路:为每位同学记录输入序号,按 (分数降序, 序号升序) 排序即可;用稳定排序(如归并/稳定版 sort 语义)时直接按分数排序也可。
复杂度:O(n log n)。
来源
人工命题 · 三方对比实验