PAT 乙级 1032：挖掘机技术哪家强 Python 高效解法

PAT 乙级 1032 挖掘机技术哪家强

题目背景 为了用事实说明挖掘机技术到底哪家强，PAT 组织了一场技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入格式： 输入在第 1 行给出不超过 10^5 的正整数 N，即参赛人数。随后 N 行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从 1 开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

输出格式： 在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入样例：

6
3 65
2 80
1 100
2 70
3 40
3 0

输出样例：

2 150

问题分析与优化思路

这道题的核心在于统计每个学校的总分。初看似乎直接用字典累加即可，但在处理大规模数据（N 可达 10^5）时，Python 的 input() 函数和异常捕获机制会成为性能瓶颈。

很多初学者会写出类似这样的代码：

n = int(input())
d = {}
for i in range(n):
    a = input().split()
    try:
        if d[int(a[0])]:
            d[int(a[0])] += int(a[1])
    except:
        d[int(a[0])] = int(a[1])

虽然逻辑上能跑通，但实际运行中往往会在最后一个测试点超时。原因主要有两点：

1. I/O 效率低：input() 在循环内被调用 N 次，每次都要进行系统调用，当 N 很大时开销显著。
2. 异常控制流开销：使用 try-except 来判断键是否存在属于滥用异常处理。在 Python 中，异常捕获的成本远高于普通的条件判断，尤其是在高频循环中。

优化方案

要解决这个问题，我们需要从输入读取和数据结构两方面入手。

1. 批量读取输入：使用 sys.stdin.read() 一次性读取所有标准输入，然后按空白字符分割。这比逐行读取快得多。
2. 简化字典操作：使用 collections.defaultdict(int) 可以自动处理键不存在的情况，无需手动判断或捕获异常，代码更简洁且执行更快。
3. 线性查找最大值：不需要对分数列表排序，直接遍历字典找出最大值即可，时间复杂度为 O(N)。

参考实现

下面是经过优化的完整代码，可以直接提交通过评测。