【05NOIP提高组】谁拿了最多奖学金

GitHub跳转原题关系图返回列表

五项奖学金条件互相独立可叠加,边读边把每人奖金累加出来;取最大值时用严格大于,并列就自然留下最早出现的那个学生。

OJ: roj

题目 ID: 1839

难度:入门

标签:模拟枚举python

创建: 2026-10-08 06:45

更新: 2026-10-08 06:45

形式化题目

给出 NN 名学生,第 ii 名学生有六项属性:姓名 namei\text{name}_i、期末平均成绩 AiA_i、 班级评议成绩 BiB_i、是否学生干部 Li∈{Y,N}L_i \in \{Y, N\}、是否西部省份学生 Wi∈{Y,N}W_i \in \{Y, N\}、 发表论文数 PiP_i。五项奖学金各自独立判定、可以叠加:

g1=8000(Ai>80∧Pi⩾1),院士奖学金g2=4000(Ai>85∧Bi>80),五四奖学金g3=2000(Ai>90),成绩优秀奖g4=1000(Ai>85∧Wi=Y),西部奖学金g5=850(Bi>80∧Li=Y),班级贡献奖 \begin{aligned} g_1 &= 8000 \quad (A_i > 80 \wedge P_i \geqslant 1), &\text{院士奖学金}\\ g_2 &= 4000 \quad (A_i > 85 \wedge B_i > 80), &\text{五四奖学金}\\ g_3 &= 2000 \quad (A_i > 90), &\text{成绩优秀奖}\\ g_4 &= 1000 \quad (A_i > 85 \wedge W_i = Y), &\text{西部奖学金}\\ g_5 &= 850 \quad (B_i > 80 \wedge L_i = Y), &\text{班级贡献奖} \end{aligned}

记第 ii 名学生的奖金总额 fi=g1+g2+g3+g4+g5f_i = g_1 + g_2 + g_3 + g_4 + g_5。求:

  1. namek\text{name}_k,其中 k=min⁡{ i:fi=max⁡jfj }k = \min\{\, i : f_i = \max_j f_j \,\}——即奖金最多者, 并列时取输入中出现最早的那一个;
  2. 该最高奖金 max⁡jfj\max_j f_j;
  3. 全员总额 ∑i=1Nfi\sum_{i=1}^{N} f_i。

数据范围:1⩽N⩽1001 \leqslant N \leqslant 100,Ai,Bi∈[0,100]A_i, B_i \in [0, 100],Pi∈[0,10]P_i \in [0, 10], 姓名是不超过 20 个大小写英文字母的非空串。

正解

思路

五项奖学金的条件两两之间没有任何耦合:一个学生能不能拿院士奖学金, 与他是不是干部、是不是西部学生完全无关;题面也明说"每项奖学金的获奖人数没有限制, 每名学生也可以同时获得多项奖学金"。所以第 ii 名学生的奖金就是一个纯组合式的加法:

fi=[Ai>80][Pi⩾1]⋅8000+[Ai>85][Bi>80]⋅4000+[Ai>90]⋅2000+[Ai>85][Wi=Y]⋅1000+[Bi>80][Li=Y]⋅850.f_i = [A_i > 80][P_i \geqslant 1] \cdot 8000 + [A_i > 85][B_i > 80] \cdot 4000 + [A_i > 90] \cdot 2000 + [A_i > 85][W_i = Y] \cdot 1000 + [B_i > 80][L_i = Y] \cdot 850 .

不需要决策、不需要排序、不需要比较不同奖项的优先级——逐条判定、逐条累加就够了。 题面给的例子正是这个意思:姚林 87/8287/82 且是干部,同时满足五四(87>85,82>8087>85, 82>80) 与班级贡献(82>8082>80 且干部),于是拿 4000+850=48504000+850=4850。

题目只要三样东西:最高奖金得主、最高奖金数额、全员总额。它从来不要一份 完整排行榜,所以也不必把 NN 名学生全存下来。做法就是单趟扫描:读到一个学生, 当场算出他的 fif_i,一路累加到 total_sum,再拿 fif_i 去和目前见过的最大值比。

比较这一步藏着本题唯一真正的陷阱。题面要求并列时输出最早出现的学生, 而我们是在扫描过程中不断刷新"目前的冠军"。如果在刷新时写 f_i >= best, 那么后面每一个与当前冠军同分的同学都会把冠军顶掉,最终留下的是最晚出现者; 写成严格大于 f_i > best,“先来者先占位、同分不覆盖”,扫描结束时留在变量里的 恰好就是最早出现的并列者。

另一个细节是最大值变量的初值。取 best = -1 而不是 0:题面虽然保证"总有同学能满足 获得奖学金的条件",但 best = -1 让第 1 个学生无论如何都能触发一次更新, 即使遇到全员奖金为 0 的退化输入(题面保证之外)也能给出确定输出而不是空姓名。

最后是边界口径。题面所有成绩都用"高于"描述,一律对应严格大于:A>80A>80、B>80B>80、 A>85A>85、B>80B>80、A>90A>90,写成 >= 就会让恰好 8080 分 / 8585 分 / 9090 分的学生多拿钱。 唯一的例外是论文篇数,"1 篇或 1 篇以上"对应 P⩾1P \geqslant 1。

代码

python
#!/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()
cpp
/**
 * 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++ 版是同一个单趟扫描。

复杂度

  • 时间复杂度:O(N)O(N)。每个学生固定做 5 次常数级条件判定,总判定次数 5N⩽5005N \leqslant 500。 N⩽100N \leqslant 100 时运行时间在微秒级,相对 1000 ms 的限制有极大量余。
  • 空间复杂度:O(1)O(1)。学生数据边读边丢,只保留 best_name / best_val / total_sum 三个变量(Python 生成器额外持有输入缓冲区本身)。

总结

本题是"读题 + 模拟"型基础题,考点全在细节而不是算法:

  1. 五项奖学金独立可叠加,别去想"先给哪个更优"这种不存在的优先级问题;
  2. 所有成绩比较都是严格大于,只有论文篇数是 ⩾1\geqslant 1;
  3. 并列取最早出现者,对应刷新最大值时用严格大于,而不是大于等于;
  4. 不需要数组也不需要排序,单趟扫描同时得到最高者和全员总额。

数值上单人上限 8000+4000+2000+1000+850=158508000+4000+2000+1000+850 = 15850,全员上限 100×15850=1585000100 \times 15850 = 1585000, 32 位整数足够,不必考虑溢出。

数据说明:本题仓库素材里带有数据生成脚本 data.py,data/ 是脚本按题面口径自造的 (含最小规模 N=1N=1、全字段最大值并列、阈值矩阵、N=100N=100 全体并列等构造点), 并非官方原数据;题面文本与 05NOIP 提高组原题一致,但生成器对边界的取舍只代表造题人 的理解。另外素材源的 std.cpp 与本文解法口径一致(同为逐条累加 + 严格大于扫描), 已按真实数据核对通过。