PAT乙级_1085 PAT单位排行_Python_AC解法_含疑难点
注意事项：
因为笔者的编程水平以自学为主，代码结构可能比较混乱、变量命名可能不够规范。
文章中的AC解法不一定最优，并且包含笔者强烈的个人风格，不喜勿喷，但欢迎在评论中理性讨论或者给出提升建议。
文章中提到的疑难点仅为个人在刷题过程中所遇到的情况，如有读者存在其他疑难点，欢迎在评论中加以补充，笔者会尽量将其加入到文章内容中。
合集：
PAT乙级_合集_Python_AC解法
题目：
1085 PAT单位排行
题目描述：
每次 PAT 考试结束后，考试中心都会发布一个考生单位排行榜。本题就请你实现这个功能。
输入格式：
输入第一行给出一个正整数 N（≤10^5），即考生人数。随后 N 行，每行按下列格式给出一个考生的信息：
准考证号 得分 学校
其中准考证号是由 6 个字符组成的字符串，其首字母表示考试的级别：B代表乙级，A代表甲级，T代表顶级；得分是 [0, 100] 区间内的整数；学校是由不超过 6 个英文字母组成的单位码（大小写无关）。注意：题目保证每个考生的准考证号是不同的。
输出格式：
首先在一行中输出单位个数。随后按以下格式非降序输出单位的排行榜：
排名 学校 加权总分 考生人数
其中排名是该单位的排名（从 1 开始）；学校是全部按小写字母输出的单位码；加权总分定义为乙级总分/1.5 + 甲级总分 + 顶级总分*1.5的整数部分；考生人数是该属于单位的考生的总人数。
学校首先按加权总分排行。如有并列，则应对应相同的排名，并按考生人数升序输出。如果仍然并列，则按单位码的字典序输出。
输入样例：
10
A57908 85 Au
B57908 54 LanX
A37487 60 au
T28374 67 CMU
T32486 24 hypu
A66734 92 cmu
B76378 71 AU
A47780 45 lanx
A72809 100 pku
A03274 45 hypu
输出样例：
5
1 cmu 192 2
1 au 192 3
3 pku 100 1
4 hypu 81 2
4 lanx 81 2
代码限制：
代码长度限制
16 KB
时间限制
800 ms
内存限制
64 MB
栈限制
8192 KB
AC解法：
import sys# 获取首行输入的总人数
n = int(input())# 逐行读取输入的成绩数据
lst = {} # 生成空字典用于统计相关数据
for _ in range(n): # 逐行遍历读取输入数据name, score, school = sys.stdin.readline().split() # 通过 sys 模块高性能读取该行输入数据school = school.lower() # 将学校名转换为小写if school not in lst: # 若该校名没被存储在字典 lst 中lst[school] = [0] * 6 # 以校名为键，长度为 6 各个初始值都为 0 的列表作为值# 值列表的各项依次用于存储 甲级总分、甲级人数、乙级总分、乙级人数、顶级总分、顶级人数if name[0] == 'A': # 若准考证号首字母为 A ，则为甲级lst[school][0] += int(score) # 甲级总分加上当前成绩lst[school][1] += 1 # 甲级人数 +1if name[0] == 'B': # 若准考证号首字母为 B ，则为乙级lst[school][2] += int(score) # 乙级总分加上当前成绩lst[school][3] += 1 # 乙级人数 +1if name[0] == 'T': # 若准考证号首字母为 T ，则为顶级lst[school][4] += int(score) # 顶级总分加上当前成绩lst[school][5] += 1 # 顶级人数 +1# 汇总成绩
ans = [] # 生成空列表用于排行榜
for school in lst.keys(): # 遍历校名sa, ca, sb, cb, st, ct = lst[school] # 取得该校的各项数据total = int(sa + sb / 1.5 + st * 1.5) # 计算该校的加权总分并直接取整cnt = ca + cb + ct # 计算该校参加考试的总人数ans.append((school, total, cnt)) # 将该校数据存入排名表中
ans.sort(key=lambda x: (-x[1], x[2], x[0]))
# 以主关键字为负的加权总分、次关键字为考试总人数、再次关键字为校名进行升序排序
# 因为排序对加权总分取负值，所以按升序排序后，可以达到实际加权总分降序的效果# 输出结果
print(len(ans)) # 输出学校数
rank = 1 # 用于表示排名，初始值为 1
for i in range(len(ans)): # 遍历排行榜if i > 0 and ans[i][1] != ans[i-1][1]: # 若当前不为排行榜首位，且当前加权总分不等于前一位的加权总分rank = i + 1 # 则排名更新为当前下标值 +1print(f"{rank} {ans[i][0]} {ans[i][1]} {ans[i][2]}") # 按格式要求拼接结果输出
题目解读：
本题描述比较易懂。
先依次获取考生信息，再对按学校对各类型成绩进行加权汇总，然后对汇总结果进行排序，最后按格式要求依次输出排行榜中的数据。
疑难点：
测试点4、测试点5运行超时/内存超限
这两个大数据量的测试点可能会同时产生运行超时和内存超限的情况。
避免运行超时的关键在于要避免统计排行榜时多次使用 sum 函数求和、多次从字典中取值。
避免内存超限的关键在于要避免对输入的不同类型考试分别独立存储、对各个成绩单独存储。
AC解法对测试点4、测试点5的内存消耗约为42000kb、45000kb，运行耗时约为450ms、630ms。
AC解法具体优化点
1、输入
import sysn = int(input()) for _ in range(n):name, score, school = sys.stdin.readline().split()import sysn = int(input()) for _ in range(n):name, score, school = input().split()第二种输入方式多消耗约70ms。
2、存储
import sysn = int(input()) lst = {} for _ in range(n):name, score, school = sys.stdin.readline().split()school = school.lower()if school not in lst:lst[school] = [0] * 6if name[0] == 'A':lst[school][0] += int(score)lst[school][1] += 1import sysn = int(input()) lst = {} for _ in range(n):name, score, school = sys.stdin.readline().split()school = school.lower()if school not in lst:lst[school] = [[], 0, [], 0, [], 0]if name[0] == 'A':lst[school][0].append(int(score))lst[school][1] += 1第二种存储方式，在后续计算加权总分时还需要使用 sum 函数求和，最终对于测试点4，多消耗内存约22000kb、多耗时约200ms；对于测试点5则会同时导致内存超限和运行超时。此外，如果对甲级、乙级、顶级的数据分别存储到三个字典中，同样也会出现类似结果。
3、读取
for school in lst.keys():sa, ca, sb, cb, st, ct = lst[school]for school in lst.keys():sa, ca = lst[school][0], lst[school][1]sb, cb = lst[school][2], lst[school][3]st, ct = lst[school][4], lst[school][5]第二种读取方式会导致要多次查询字典，多耗时约50ms。
测试点4、测试点5运行超时/内存超限总结
本题中这两个测试点超出限制是多种因素造成的，需要对多个方面进行优化，其中最关键的还是对获取到的输入数据的存储，要理清题意，仅对必要的数据选择合适的方式进行存储。
其他注意事项
1、
经测试，虽然本题计算加权总分时，无论是在读取到各类型成绩后就进行加权、最后再求和，还是读取时仅保留原始值、最后单独各类型求和后时再加权计算总分，都可以通过所有测试点，但是因为加权过程中会出现小数点，因此第一种方式是不严谨的，建议选择第二种方式计算加权总分。