红军补给均衡：相邻站点调拨统计 完整解题档案

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：10
• 训练题主题：红军补给均衡：相邻站点调拨统计
• 所属赛道：红色文化赛道

题目背景

红军补给路线上的多个站点当前持有不同数量的补给箱，指挥员希望把它们均衡到相同数量。每次调拨只允许跨相邻站点边界搬运任意整数箱，因此需要先判断是否可均分，再统计最少经过多少条边界和总搬运量。

任务描述

• 判断总补给箱数是否能被站点数整除。
• 若可均分，计算最少跨边界调拨次数。
• 统计最少总调拨箱数。

输入格式

1. 第一行输入 n，表示站点数量。
2. 第二行输入 n 个整数，表示各站点当前补给箱数。

输出格式

1. 若总数不能均分，输出 possible=NO。
2. 若可均分，依次输出 possible=YES、moves=最少跨边界调拨次数、units=最少总调拨箱数。

数据范围与说明

• 1 <= n <= 2 * 10^5。
• 0 <= a[i] <= 10^9。
• 只能在相邻站点之间调拨。
• 若总和不能被 n 整除则无解。
• 总搬运箱数要使用 64 位整数。

样例输入

5
1 5 3 7 4

样例输出

possible=YES
moves=3
units=8

样例解释

• 总补给为 20，平均到 5 个站点后目标值是 4。
• 顺序计算前缀差值得到 -3, -2, -3, 0，其中有三条边界必须调拨。
• 总搬运量为 3 + 2 + 3 = 8。

知识点清单

• 平均数可行性判断。
• 前缀差值表示左侧净盈亏。
• 非零前缀差值对应必须跨越的边界。
• sum(abs(prefix_diff)) 的意义。
• 线性扫描与 64 位累计。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n <= 2 * 10^5。
• 0 <= a[i] <= 10^9。
• 只能在相邻站点之间调拨。
• 若总和不能被 n 整除则无解。
• 总搬运箱数要使用 64 位整数。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 前缀差值贪心 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 总和不能整除时必须直接输出 possible=NO。
• 最后一个站点不需要继续向右搬运，因此只扫描到 n-1。
• 所有站点初始就相等时，moves 和 units 都应为 0。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：optimization
• 主算法：前缀差值贪心

判题重点

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

公开样例建议

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

隐藏数据建议

• 准备总和无法均分的用例，确认程序立即终止到无解输出。
• 准备所有站点已均衡的用例，检查零调拨情况。
• 准备长链大数值数据，验证 64 位累加。

验收清单

源文件：acceptance-checklist.md

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

样例输入输出

样例输入：sample.in

5
1 5 3 7 4

样例输出：sample.out

possible=YES
moves=3
units=8

题解、建模与最终解法

自动整理的解题流程

• 题目主题：红军补给均衡：相邻站点调拨统计
• 题目摘要：通过前缀差值分析站点间的净盈亏，计算最少调拨边界数和总搬运箱数。
• 判题提示：该题以优化求解为主，重点是约束建模、可行性检查和最优值维护。
• 先完成节点、边和资源约束建模，再决定是否使用最短路、枚举或状态扩展搜索。
• 输出不仅要有总代价，还要确认路线和资源变化与最优值同步更新。

解题思路

源文件：solution-rationale.md

1. 问题重述

通过前缀差值分析站点间的净盈亏，计算最少调拨边界数和总搬运箱数。

2. 数据结构与建模

• 主算法：前缀差值贪心
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 先求总和并判断能否均分到每个站点。
2. 把每个站点相对目标值的盈亏顺序累加成前缀差值。
3. 每个非零前缀差值都代表一条必须发生调拨的边界。
4. 对所有非零前缀差值取绝对值累加，得到最少总搬运量。

4. 正确性说明

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

5. 复杂度分析

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

6. 易错点

• 总和不能整除时必须直接输出 possible=NO。
• 最后一个站点不需要继续向右搬运，因此只扫描到 n-1。
• 所有站点初始就相等时，moves 和 units 都应为 0。

7. 知识点清单

• 平均数可行性判断。
• 前缀差值表示左侧净盈亏。
• 非零前缀差值对应必须跨越的边界。
• sum(abs(prefix_diff)) 的意义。
• 线性扫描与 64 位累计。

设计决策记录

源文件：decision-log.md

• 选择 前缀差值贪心 作为主算法，因为它能直接覆盖题目的核心约束。
• 题目的相邻调拨限制可以完全转化为前缀盈亏平衡问题。
• 只要掌握每条边界左侧的净盈亏，就能得到最少调拨信息。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 准备总和无法均分的用例，确认程序立即终止到无解输出。
• 准备所有站点已均衡的用例，检查零调拨情况。
• 准备长链大数值数据，验证 64 位累加。
• 最后再补 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)
    values = [next(it) for _ in range(n)]
    total = sum(values)
    if total % n != 0:
        return "possible=NO"
    target = total // n
    prefix_diff = 0
    moves = 0
    units = 0
    for index in range(n - 1):
        prefix_diff += values[index] - target
        if prefix_diff != 0:
            moves += 1
            units += abs(prefix_diff)
    return "\n".join(
        [
            "possible=YES",
            f"moves={moves}",
            f"units={units}",
        ]
    )


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

C++ 对照实现

源文件：main.cpp

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

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

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

    int n;
    if (!(cin >> n)) {
        return 0;
    }
    vector<long long> values(n);
    long long total = 0;
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
        total += values[i];
    }
    if (total % n != 0) {
        cout << "possible=NO\n";
        return 0;
    }
    long long target = total / n;
    long long prefix_diff = 0;
    long long units = 0;
    int moves = 0;
    for (int i = 0; i < n - 1; ++i) {
        prefix_diff += values[i] - target;
        if (prefix_diff != 0) {
            ++moves;
            units += llabs(prefix_diff);
        }
    }
    cout << "possible=YES\n";
    cout << "moves=" << moves << "\n";
    cout << "units=" << units << "\n";
    return 0;
}

代码执行与运行结果

最新成功运行

PY 运行输出摘录

possible=YES
moves=3
units=8

CPP 运行输出摘录

possible=YES
moves=3
units=8

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s2-jh-06-supply-balance/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s2-jh-06-supply-balance/02-solution
• 运行证据：10-cases/s2-jh-06-supply-balance/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