题意

输入若干同学的姓名和生日，按年龄从大到小输出姓名。年龄大等价于生日更早。

如果两个人生日完全相同，后输入的人先输出。

思路

这是多关键字排序。

对每个同学保存：

1(年, 月, 日, -输入顺序, 姓名)

Python 元组会从左到右比较。年月日越小，生日越早，年龄越大；同一天生日时，输入顺序越靠后，-输入顺序 越小，也就排得越前。

排序后依次输出姓名即可。

Python 知识

• name, year, month, day = input().split() 可以同时读取一个字符串和三个数字字段。
• 元组天然支持多关键字排序，students.sort() 会按第 1 项、第 2 项、第 3 项依次比较。
• 字符串字段 year/month/day 要转成 int，否则字符串比较会按字典序，不是数字大小。

参考笔记：

• /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
• /home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md

代码

1
2
3
4
5
6
7
8
9
10
11n = int(input())

students = []
for order in range(n):
    name, year, month, day = input().split()
    students.append((int(year), int(month), int(day), -order, name))

students.sort()

for student in students:
    print(student[4])

Pythonic 写法

元组排序：

1
2
3
4
5
6
7n = int(input())
students = []
for order in range(n):
    name, y, m, d = input().split()
    students.append((int(y), int(m), int(d), -order, name))
for *_, name in sorted(students):
    print(name)

复杂度

时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$。

总结

多关键字排序时，先把题目的比较规则逐项写出来，再把它翻译成一个元组排序键。