#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)。

来源

人工命题 · 三方对比实验