每日一题——Python代码实现PAT乙级1082 射击比赛（举一反三+思想解读+逐步优化）四千字好文_python比赛题

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

目录

我的写法

代码分析

代码步骤

时间复杂度分析

空间复杂度分析

总结

我要更强

时间复杂度分析

空间复杂度分析

总结

哲学和编程思想

KISS原则（Keep It Simple, Stupid）：

YAGNI原则（You Ain't Gonna Need It）：

效率优化：

数据结构的选择：

函数式编程思想：

抽象和模块化：

实用主义：

举一反三

---

题目链接：https://pintia.cn/problem-sets/994805260223102976/exam/problems/type/7?problemSetProblemId=994805260990660608&page=0

我的写法

n=int(input())
player_scores=[]
for i in range(n):
    player_score=input().split()
    player_score[1]=int(player_score[1])
    player_score[2]=int(player_score[2])
    player_scores.append([player_score[0],player_score[1]**2+player_score[2]**2])
    
ranking=sorted(player_scores,key=lambda x: x[1])
print(f"{ranking[0][0]} {ranking[-1][0]}")

代码分析

这段代码实现了射击比赛的排名功能，根据输入的运动员编号和射击坐标，计算每个运动员的得分（距离靶心的平方和），然后对运动员进行排序，最后输出得分最低（冠军）和最高（菜鸟）的运动员编号。

代码步骤

1. 输入处理：
   • 读取运动员数量 n。
   • 循环读取每个运动员的信息，包括编号和射击坐标，计算得分（距离的平方和），并将编号和得分存储在列表 player_scores 中。
2. 排序：
   • 使用 sorted() 函数对 player_scores 列表进行排序，排序的关键字是每个运动员的得分。
3. 输出：

• 输出得分最低的运动员编号（即排序后列表的第一个元素的编号）和得分最高的运动员编号（即排序后列表的最后一个元素的编号）。

时间复杂度分析

1. 输入处理：
   • 读取 n 个运动员的信息，每个运动员的信息处理包括字符串分割和整数转换，时间复杂度为 O(n)。
2. 排序：
   • 使用 sorted() 函数对包含 n 个元素的列表进行排序，时间复杂度为 O(n log n)。
3. 输出：

• 输出操作的时间复杂度为 O(1)。

总时间复杂度为 O(n + n log n)，即 O(n log n)。

空间复杂度分析

1. 存储运动员信息：
   • 使用列表 player_scores 存储所有运动员的编号和得分，空间复杂度为 O(n)。
2. 其他变量：

• 除了输入和输出的变量外，没有使用额外的数据结构，空间复杂度为 O(1)。

总空间复杂度为 O(n)。

总结

这段代码有效地解决了射击比赛的排名问题，时间复杂度主要受排序操作影响，为 O(n log n)，空间复杂度为 O(n)。代码结构清晰，逻辑简单，适合处理中小规模的数据集。对于大规模数据集，可能需要考虑更高效的排序算法或数据结构来优化性能。

---

我要更强

为了优化时间复杂度和空间复杂度，我们可以考虑以下几点：

1. 避免不必要的排序：我们只需要找到距离最小的和最大的，不需要对所有数据进行排序。
2. 使用更有效的数据结构：例如，使用字典（dict）来存储运动员的编号和得分，可以快速查找。
3. 减少内存分配：避免在循环中进行大量的列表追加操作，这可能会导致多次内存分配。

下面是优化后的代码：

# 读取运动员数量
n = int(input())
 
# 初始化字典存储运动员信息
player_scores = {}
 
# 读取每个运动员的信息并计算得分
for _ in range(n):
    # 读取一行输入，分割成列表
    player_info = input().split()
    # 运动员编号
    player_id = player_info[0]
    # 射击坐标
    x, y = map(int, player_info[1:])
    # 计算得分（距离的平方和）
    score = x**2 + y**2
    # 存储到字典中
    player_scores[player_id] = score
 
# 找到得分最小的运动员
min_score_player = min(player_scores, key=player_scores.get)
# 找到得分最大的运动员
max_score_player = max(player_scores, key=player_scores.get)
 
# 输出结果
print(f"{min_score_player} {max_score_player}")

时间复杂度分析

1. 输入处理：
   • 读取 n 个运动员的信息，每个运动员的信息处理包括字符串分割和整数转换，时间复杂度为 O(n)。
2. 查找最小和最大得分：

• 使用 min() 和 max() 函数查找字典中的最小和最大值，时间复杂度为 O(n)。

总时间复杂度为 O(n)。

空间复杂度分析

1. 存储运动员信息：

• 使用字典 player_scores 存储所有运动员的编号和得分，空间复杂度为 O(n)。

总空间复杂度为 O(n)。

总结

这段优化后的代码避免了不必要的排序操作，使用字典来存储和快速查找运动员信息，有效地减少了时间复杂度和空间复杂度。时间复杂度从 O(n log n) 降低到 O(n)，空间复杂度保持为 O(n)。这种优化特别适用于处理大规模数据集，可以显著提高程序的执行效率。

---

哲学和编程思想

优化这段代码所使用的方法体现了以下哲学和编程思想：

1. KISS原则（Keep It Simple, Stupid）：

   • 代码简洁明了，避免不必要的复杂性。例如，使用字典直接存储和查找运动员信息，而不是通过排序来找到最小和最大值。

2. YAGNI原则（You Ain't Gonna Need It）：

   • 只实现当前需要的功能，不预先实现未来可能需要的功能。在这个例子中，我们只关注找到最小和最大值的运动员，而不是对所有运动员进行排序。

3. 效率优化：

   • 通过减少不必要的数据处理和排序，提高了程序的执行效率。这体现了对时间和空间复杂度的关注，是算法和数据结构设计中的重要思想。

4. 数据结构的选择：

   • 使用字典（dict）作为数据结构，利用了字典在查找操作上的高效性（平均时间复杂度为O(1)）。这体现了在编程中选择合适数据结构的重要性。

5. 函数式编程思想：

   • 使用 map() 函数将字符串转换为整数，以及使用 min() 和 max() 函数直接找到最小和最大值，这些都体现了函数式编程中避免副作用、强调函数组合和使用高阶函数的思想。

6. 抽象和模块化：

   • 代码中的每个部分都有明确的功能，如输入处理、数据存储、结果查找和输出。这种模块化的设计使得代码更易于理解和维护。

7. 实用主义：

• 代码的优化是基于实际需求和性能考虑，而不是追求理论上的最优解。这种实用主义的态度在实际编程中非常重要，它确保了代码既高效又易于理解和维护。

通过这些哲学和编程思想的应用，能够编写出既高效又易于理解的代码，这是软件开发中的一个重要目标。

---

举一反三

基于上述哲学和编程思想，以下是一些实用的技巧和建议，可以帮助在编程中举一反三：

1. 保持代码简洁：
   • 避免过度设计，只实现当前明确需要的功能。
   • 使用简单的数据结构和算法，除非有明确的性能需求。
   • 编写清晰、直观的代码，避免复杂的控制流和嵌套。
2. 选择合适的数据结构：
   • 根据操作的类型（如查找、插入、删除）选择最合适的数据结构。
   • 了解不同数据结构的性能特点，如数组、链表、栈、队列、树、图、哈希表等。
   • 在需要快速查找的地方使用哈希表（如Python中的字典）。
3. 优化时间和空间复杂度：
   • 分析算法的时间和空间复杂度，寻找优化的机会。
   • 避免不必要的计算和数据复制。
   • 使用缓存或记忆化技术来避免重复计算。
4. 函数式编程技巧：
   • 使用高阶函数（如map、filter、reduce）来处理数据集合。
   • 利用函数式编程的不可变性和纯函数来减少副作用。
   • 使用递归或迭代来处理问题，根据问题的特性选择最合适的方法。
5. 模块化和抽象：
   • 将代码分解为小的、可重用的模块。
   • 使用抽象来隐藏实现细节，提供清晰的接口。
   • 编写测试来确保模块的正确性和独立性。
6. 实用主义：
   • 根据实际需求和性能目标来选择解决方案。
   • 不要为了追求理论上的最优解而牺牲代码的可读性和可维护性。
   • 在实际应用中不断测试和调整，以找到最适合的解决方案。
7. 持续学习和实践：

• 阅读和分析优秀的代码，学习他人的编程技巧。
• 参与开源项目，实践和提升编程技能。
• 定期回顾和重构自己的代码，不断提高代码质量。

通过应用这些技巧和建议，可以在编程中更加灵活和高效，同时也能够提升代码的质量和可维护性。记住，编程是一个不断学习和实践的过程，不断挑战自己，尝试新的方法和技巧，将有助于成为一个更好的程序员。

---