红色讲解队编组：训练时长内积分最大化 代码附录

• 完整解题档案：complete-solution-dossier.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;
}