五项奖学金条件互相独立可叠加,边读边把每人奖金累加出来;取最大值时用严格大于,并列就自然留下最早出现的那个学生。
OJ: roj
题目 ID: 1839
难度:入门
标签:模拟枚举python
创建: 2026-10-08 06:45
更新: 2026-10-08 06:45
形式化题目
给出
记第
,其中 ——即奖金最多者, 并列时取输入中出现最早的那一个; - 该最高奖金
; - 全员总额
。
数据范围:
正解
思路
五项奖学金的条件两两之间没有任何耦合:一个学生能不能拿院士奖学金,
与他是不是干部、是不是西部学生完全无关;题面也明说"每项奖学金的获奖人数没有限制,
每名学生也可以同时获得多项奖学金"。所以第
不需要决策、不需要排序、不需要比较不同奖项的优先级——逐条判定、逐条累加就够了。
题面给的例子正是这个意思:姚林
题目只要三样东西:最高奖金得主、最高奖金数额、全员总额。它从来不要一份
完整排行榜,所以也不必把 total_sum,再拿
比较这一步藏着本题唯一真正的陷阱。题面要求并列时输出最早出现的学生,
而我们是在扫描过程中不断刷新"目前的冠军"。如果在刷新时写 f_i >= best,
那么后面每一个与当前冠军同分的同学都会把冠军顶掉,最终留下的是最晚出现者;
写成严格大于 f_i > best,“先来者先占位、同分不覆盖”,扫描结束时留在变量里的
恰好就是最早出现的并列者。
另一个细节是最大值变量的初值。取 best = -1 而不是 0:题面虽然保证"总有同学能满足
获得奖学金的条件",但 best = -1 让第 1 个学生无论如何都能触发一次更新,
即使遇到全员奖金为 0 的退化输入(题面保证之外)也能给出确定输出而不是空姓名。
最后是边界口径。题面所有成绩都用"高于"描述,一律对应严格大于:>= 就会让恰好
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 06:45
# update_at: 2026-10-08 06:45
import sys
from collections.abc import Iterator
# 五项奖学金的判定条件与金额:(期末成绩下界, 评议成绩下界, 需要干部, 需要西部, 论文下界)
# 成绩下界都按题面"高于"取严格大于,写成"最小成立值";不需要的维度填 0 / 0 / False。
type Rule = tuple[int, int, bool, bool, int] # avg_min, cls_min, leader, west, papers_min
RULES: tuple[tuple[Rule, int], ...] = (
((81, 0, False, False, 1), 8000), # 院士奖学金:avg>80 且 papers>=1
((86, 81, False, False, 0), 4000), # 五四奖学金:avg>85 且 cls>80
((91, 0, False, False, 0), 2000), # 成绩优秀奖:avg>90
((86, 0, False, True, 0), 1000), # 西部奖学金:avg>85 且西部省份学生
((0, 81, True, False, 0), 850), # 班级贡献奖:cls>80 且学生干部
)
def students(data: Iterator[str]) -> Iterator[tuple[str, int]]:
"""依次产出每个学生的 (姓名, 奖金总额)。
五项奖学金互相独立、可叠加,逐条判定后求和即可;
学生属性读完即弃,不需要保存全量数据。
"""
n = int(next(data))
for _ in range(n):
name = next(data)
avg, cls = int(next(data)), int(next(data))
leader, west = next(data) == 'Y', next(data) == 'Y'
papers = int(next(data))
yield name, sum(
money
for (avg_min, cls_min, need_leader, need_west, papers_min), money in RULES
if avg >= avg_min and cls >= cls_min
and (not need_leader or leader) and (not need_west or west)
and papers >= papers_min
)
def solve() -> None:
data = iter(sys.stdin.buffer.read().decode().split()) # 姓名按字符串处理,整体解码
total_sum = 0 # 全员奖学金总额
best_val = -1 # 初值 -1:即使全员 0 元也能让第 1 个人完成初始化
best_name = '' # 最高奖金获得者(并列时保留最早出现的)
for name, money in students(data):
total_sum += money
if money > best_val: # 严格大于:并列时不覆盖,最早出现者胜出
best_val, best_name = money, name
print(f"{best_name}\n{best_val}\n{total_sum}")
if __name__ == "__main__":
solve()/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 06:45
* update_at: 2026-10-08 06:45
*/
// main.cpp:谁拿了最多奖学金(05NOIP 提高组 / 一本通 1839)。
// 与 main.py 同一算法:五项奖学金条件互相独立、可叠加,边读边算;
// 维护"最高奖金"时用严格大于,天然满足"并列取最早出现者"。
//
// 判读依据(与 content.md 逐条对照):
// 1) 院士奖学金 8000:avg > 80 且 papers >= 1("1 篇或 1 篇以上"取 >=)
// 2) 五四奖学金 4000:avg > 85 且 cls > 80
// 3) 成绩优秀奖 2000:avg > 90
// 4) 西部奖学金 1000:avg > 85 且 west == 'Y'
// 5) 班级贡献奖 850:cls > 80 且 leader == 'Y'
// 题面所有成绩都是"高于",一律严格大于;只有论文篇数是"1 篇或以上",取 >=。
// 单人上限 8000+4000+2000+1000+850 = 15850,n <= 100 ⇒ 总和上限 1585000,int 足够。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0; // 无输入时安全退出
int best_val = -1; // 初值 -1:即使全员 0 元也能让第 1 个人完成初始化
string best_name; // 最高奖金获得者(并列时保留最早出现的)
int total_sum = 0; // 全员奖学金总额
for (int i = 0; i < n; i++) {
string name;
int avg, cls, papers; // 期末平均成绩 / 班级评议成绩 / 论文篇数
char leader, west; // 是否学生干部 / 是否西部省份学生:Y 或 N
cin >> name >> avg >> cls >> leader >> west >> papers;
int money = 0; // 当前学生各项奖学金之和
if (avg > 80 && papers >= 1) money += 8000; // 院士奖学金
if (avg > 85 && cls > 80) money += 4000; // 五四奖学金
if (avg > 90) money += 2000; // 成绩优秀奖
if (avg > 85 && west == 'Y') money += 1000; // 西部奖学金
if (cls > 80 && leader == 'Y') money += 850; // 班级贡献奖
total_sum += money;
if (money > best_val) { // 严格大于:并列时不覆盖,最早出现者胜出
best_val = money;
best_name = name;
}
}
cout << best_name << "\n" << best_val << "\n" << total_sum << "\n";
return 0;
}C++ 版把五项判定写成五条 if,money > best_val 完成严格大于的刷新;
Python 版把五项条件整理成一张常量表 RULES——每行是
(期末下界, 评议下界, 需要干部, 需要西部, 论文下界) 与金额,
判定时对每个学生把表里的条件逐条比对,用生成器求和,
所以"五项"这件事只出现一次,以后要加奖种只需要往表里加一行。
Python 版把学生序列写成生成器 students(),每次产出一对 (姓名, 奖金总额);
主流程只负责累加总数、比较最大值,与 C++ 版是同一个单趟扫描。
复杂度
- 时间复杂度:
。每个学生固定做 5 次常数级条件判定,总判定次数 。 时运行时间在微秒级,相对 1000 ms 的限制有极大量余。 - 空间复杂度:
。学生数据边读边丢,只保留 best_name/best_val/total_sum三个变量(Python 生成器额外持有输入缓冲区本身)。
总结
本题是"读题 + 模拟"型基础题,考点全在细节而不是算法:
- 五项奖学金独立可叠加,别去想"先给哪个更优"这种不存在的优先级问题;
- 所有成绩比较都是严格大于,只有论文篇数是
; - 并列取最早出现者,对应刷新最大值时用严格大于,而不是大于等于;
- 不需要数组也不需要排序,单趟扫描同时得到最高者和全员总额。
数值上单人上限
数据说明:本题仓库素材里带有数据生成脚本
data.py,data/是脚本按题面口径自造的 (含最小规模、全字段最大值并列、阈值矩阵、 全体并列等构造点), 并非官方原数据;题面文本与 05NOIP 提高组原题一致,但生成器对边界的取舍只代表造题人 的理解。另外素材源的 std.cpp与本文解法口径一致(同为逐条累加 + 严格大于扫描), 已按真实数据核对通过。