刷题笔记合集🔗

冠亚军排名，奖牌榜排名

问题描述

小基 即将参加一场体育竞赛，她对即将到来的比赛奖牌榜情况非常关注。比赛奖牌榜的排名规则如下：

1. 首先金牌数量多的排在前面。
2. 其次银牌数量多的排在前面。
3. 然后铜牌数量多的排在前面。
4. 若以上三个条件仍无法区分名次，则以国家名称的字典顺序排定。

我们假设国家名称不超过二十个字符，各类奖牌数不超过 ，且大于 。

输入格式

第一行输入一个整数 （），代表国家数量。

然后接下来的 行，每行包含：

一个字符串 表示各个国家的名称和三个整数 表示每个获得的金牌、银牌、铜牌的数量，以空格隔开，如（China 51 20 21）。

输出格式

输出奖牌榜的依次顺序，只输出国家名称，各占一行。

样例输入

5
China 32 28 34
England 12 34 22
France 23 33 2
Japan 12 34 25
Rusia 23 43 0

样例输出

China
Rusia
France
Japan
England

数据范围

样例	解释说明
样例1	按照规则排序，China金牌数最多排第一，Rusia和France金牌数相同，但Rusia银牌数多，所以Rusia第二，France第三，Japan和England金牌数相同，银牌数也相同，但Japan铜牌数多，所以Japan第四，England第五。

• 
• 
• 

题解

这道题要求我们按照特定规则对国家进行排序，规则包括金牌数、银牌数、铜牌数以及国家名称的字典序。

解题思路很直接：将各国信息存储起来，然后按照规则排序。可以使用各种语言内置的排序功能，只需定义好比较规则即可。

比如在Python中，可以用sort函数的key参数指定排序规则。具体做法是：按金牌数降序排列，如果金牌数相同则按银牌数降序排列，如果银牌数也相同则按铜牌数降序排列，若三者都相同则按国家名称的字典顺序排列。

对于排序规则，可以利用元组的比较特性，使用负数来实现降序排序。例如：(-gold, -silver, -bronze, name)，这样按元组的字典序排序就能满足题目要求。

时间复杂度分析：排序的时间复杂度为O(NlogN)，其中N是国家数量。由于题目限制N小于21，因此算法效率非常高，完全足够处理题目数据范围。

空间复杂度：需要O(N)的额外空间存储国家信息。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
nations = []

# 读取所有国家的信息
for _ in range(n):
    info = input().split()
    # 提取国家名称和奖牌数
    name = info[0]
    gold, silver, bronze = map(int, info[1:])
    nations.append((name, gold, silver, bronze))

# 排序函数
def sort_medal_table(nations):
    # 按金牌数降序、银牌数降序、铜牌数降序和国家名称字典序排序
    nations.sort(key=lambda x: (-x[1], -x[2], -x[3], x[0]))
    return [nation[0] for nation in nations]  # 返回排序后的国家名单

# 输出结果
result = sort_medal_table(nations)
for nation in result:
    print(nation)

• Cpp

#include <bits/stdc