刷题笔记合集🔗

问题描述

2012伦敦奥运会即将到来,大家都非常关注奖牌榜的情况。现在我们假设奖牌榜的排名规则如下:

1. 首先gold medal数量多的排在前面
2. 其次silver medal数量多的排在前面
3. 然后bronze medal数量多的排在前面
4. 若以上三个条件仍无法区分名次,则以国家名称的字典顺序排定

我们假设:

• 国家名称不超过20个字符
• 各类奖牌数不超过100且大于0

输入格式

第一行输入一个整数N(0<N<21),代表国家数量。

接下来N行,每行包含:

• 一个字符串Name表示国家名称
• 三个整数Gi,Si,Bi表示gold,silver,bronze medal的数量
• 以空格分隔,如:China 51 20 21

输出格式

按排名规则输出国家名称,每个国家占一行。

样例1

输入:

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

说明:

• China金牌最多(32),排第一
• France和Rusia金牌相同(23),但Rusia银牌多(43>33),所以Rusia排第二
• Japan和England金牌相同(12),银牌相同(34),但Japan铜牌多(25>22),所以Japan排第四

题解

这道题目可以使用排序来解决:

1. 定义国家类,包含名称和三种奖牌数
2. 实现排序比较规则:
   • 优先比较金牌数
   • 金牌相同比较银牌数
   • 银牌相同比较铜牌数
   • 都相同按国家名称字典序
3. 排序后输出国家名称

时间复杂度为 ,其中 是国家数量。

参考代码

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

for i in range(n):
    name, gold, silver, bronze = input().split()
    countries.append([int(gold), int(silver), int(bronze), name])

# 排序输出
countries.sort(key=lambda x: (-x[0], -x[1], -x[2], x[3]))
for c in countries:
    print(c[3])

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        Country[] countries = new Country[n];
        for(int i = 0; i < n; i++) {