红色讲解队编组：训练时长内积分最大化 完整解题档案

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：10
• 训练题主题：红色讲解队编组：训练时长内积分最大化
• 所属赛道：红色文化赛道

题目背景

讲解队要在有限训练时长内挑选成员参加强化训练。每名成员需要一定训练时长，同时能贡献一定积分。队伍目标是先最大化总积分，再最小化总训练时长，最后最小化入选人数。

任务描述

• 读取候选成员的训练时长和积分。
• 在总时长不超过 H 的前提下，找到最大总积分。
• 若最大积分有多种方案，再依次最小化总训练时长和入选人数。

输入格式

1. 第一行输入 n H，表示候选成员数和总训练时长上限。
2. 接下来 n 行每行输入 h v，表示一名成员的时长和积分。

输出格式

1. 第一行输出 best_score=最大总积分。
2. 第二行输出 used_hours=达到该积分时的最少总时长。
3. 第三行输出 team_size=在前两项都最优时的最少入选人数。

数据范围与说明

• 1 <= n <= 60。
• 1 <= H <= 2000。
• 1 <= h <= H，0 <= v <= 10000。
• 每名成员最多选一次。
• 比较规则是先积分最大，再总时长最小，再人数最少。

样例输入

4 7
2 6
3 8
4 9
5 12

样例输出

best_score=18
used_hours=7
team_size=2

样例解释

• 选择时长为 2 和 5 的两名成员，可得到总积分 18。
• 这个方案总时长为 7，已达到最大积分且无法再减少时长。
• 达到同样积分时也无法用更少人数完成，因此 team_size=2。

知识点清单

• 0/1 背包状态设计。
• 容量倒序枚举防止重复选取。
• 固定容量下的多关键字最优值维护。
• 不可达状态初始化。
• 从整张 DP 表中提取最终答案。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n <= 60。
• 1 <= H <= 2000。
• 1 <= h <= H，0 <= v <= 10000。
• 每名成员最多选一次。
• 比较规则是先积分最大，再总时长最小，再人数最少。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 0/1 背包动态规划 + 并列规则比较 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 即使不选任何成员也算一种合法状态，因此容量 0 要正确初始化。
• 多个容量可以达到同一最大积分时，必须取最小时长。
• 同一容量下若积分相同，还要继续比较人数。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：optimization
• 主算法：0/1 背包动态规划 + 并列规则比较

判题重点

• 重点校验建模是否正确、最优值维护是否稳定、路径或方案恢复是否完整。
• 隐藏数据会覆盖不可达、同值竞争和多约束并存情形。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 准备多个方案积分相同但时长不同的用例，检查二级规则。
• 准备积分和时长都相同但人数不同的用例，检查三级规则。
• 准备上限较小和成员数量较少的极简样例，核对初始化。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• cpp 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

4 7
2 6
3 8
4 9
5 12

样例输出：sample.out

best_score=18
used_hours=7
team_size=2

题解、建模与最终解法

自动整理的解题流程

• 题目主题：红色讲解队编组：训练时长内积分最大化
• 题目摘要：在总训练时长上限内用 0/1 背包选人，最大化积分并处理多级并列规则。
• 判题提示：该题以优化求解为主，重点是约束建模、可行性检查和最优值维护。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

解题思路

源文件：solution-rationale.md

1. 问题重述

在总训练时长上限内用 0/1 背包选人，最大化积分并处理多级并列规则。

2. 数据结构与建模

• 主算法：0/1 背包动态规划 + 并列规则比较
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 用 scores[c] 记录恰好使用 c 小时时的最大积分，并维护对应最少人数。
2. 逐个成员倒序枚举容量，避免同一成员被重复选入。
3. 容量更新时先比较积分，再比较人数。
4. DP 完成后扫描 0..H，按积分、时长、人数三层规则挑出全局最优答案。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 即使不选任何成员也算一种合法状态，因此容量 0 要正确初始化。
• 多个容量可以达到同一最大积分时，必须取最小时长。
• 同一容量下若积分相同，还要继续比较人数。

7. 知识点清单

• 0/1 背包状态设计。
• 容量倒序枚举防止重复选取。
• 固定容量下的多关键字最优值维护。
• 不可达状态初始化。
• 从整张 DP 表中提取最终答案。

设计决策记录

源文件：decision-log.md

• 选择 0/1 背包动态规划 + 并列规则比较 作为主算法，因为它能直接覆盖题目的核心约束。
• 题目具备容量限制和选或不选的结构，是标准 0/1 背包。
• 由于最终比较规则有三层，需要把并列处理写进状态更新和答案提取两处。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 准备多个方案积分相同但时长不同的用例，检查二级规则。
• 准备积分和时长都相同但人数不同的用例，检查三级规则。
• 准备上限较小和成员数量较少的极简样例，核对初始化。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

import sys


def solve(data: str) -> str:
    tokens = list(map(int, data.split()))
    if not tokens:
        return ""
    it = iter(tokens)
    n = next(it)
    limit = next(it)
    items = [(next(it), next(it)) for _ in range(n)]
    scores = [-1] * (limit + 1)
    counts = [10 ** 9] * (limit + 1)
    scores[0] = 0
    counts[0] = 0
    for hours, value in items:
        for used in range(limit, hours - 1, -1):
            prev_score = scores[used - hours]
            if prev_score == -1:
                continue
            cand_score = prev_score + value
            cand_count = counts[used - hours] + 1
            if cand_score > scores[used] or (cand_score == scores[used] and cand_count < counts[used]):
                scores[used] = cand_score
                counts[used] = cand_count
    best_score = -1
    best_hours = 0
    best_size = 0
    for used in range(limit + 1):
        if scores[used] == -1:
            continue
        candidate = (scores[used], -used, -counts[used])
        current = (best_score, -best_hours, -best_size)
        if best_score == -1 or candidate > current:
            best_score = scores[used]
            best_hours = used
            best_size = counts[used]
    return "\n".join(
        [
            f"best_score={best_score}",
            f"used_hours={best_hours}",
            f"team_size={best_size}",
        ]
    )


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

C++ 对照实现

源文件：main.cpp

• 实现状态：当前已有可执行实现

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, limit;
    if (!(cin >> n >> limit)) {
        return 0;
    }
    vector<pair<int, int>> items(n);
    for (int i = 0; i < n; ++i) {
        cin >> items[i].first >> items[i].second;
    }
    vector<long long> scores(limit + 1, -1);
    vector<int> counts(limit + 1, 1e9);
    scores[0] = 0;
    counts[0] = 0;
    for (const auto& item : items) {
        int hours = item.first;
        int value = item.second;
        for (int used = limit; used >= hours; --used) {
            if (scores[used - hours] == -1) {
                continue;
            }
            long long cand_score = scores[used - hours] + value;
            int cand_count = counts[used - hours] + 1;
            if (cand_score > scores[used] || (cand_score == scores[used] && cand_count < counts[used])) {
                scores[used] = cand_score;
                counts[used] = cand_count;
            }
        }
    }
    long long best_score = -1;
    int best_hours = 0;
    int best_size = 0;
    for (int used = 0; used <= limit; ++used) {
        if (scores[used] == -1) {
            continue;
        }
        if (best_score == -1 || scores[used] > best_score ||
            (scores[used] == best_score && used < best_hours) ||
            (scores[used] == best_score && used == best_hours && counts[used] < best_size)) {
            best_score = scores[used];
            best_hours = used;
            best_size = counts[used];
        }
    }
    cout << "best_score=" << best_score << "\n";
    cout << "used_hours=" << best_hours << "\n";
    cout << "team_size=" << best_size << "\n";
    return 0;
}

代码执行与运行结果

最新成功运行

PY 运行输出摘录

best_score=18
used_hours=7
team_size=2

CPP 运行输出摘录

best_score=18
used_hours=7
team_size=2

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s2-jh-08-team-roster/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s2-jh-08-team-roster/02-solution
• 运行证据：10-cases/s2-jh-08-team-roster/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md