坐地铁 — 题解¶

解法比较¶

出题人解法用堆选择当前边际收益最大的路段，用线段树维护等待余量，并一次压缩到下一个事件：预算用完、路段长度归零，或某站等待余量归零。后一事件把收益影响区间截断，需要更新后续候选。只在这些事件处重算，避免按预算单位逐次操作；下文的边际收益与事件数量证明沿用这一思路。

实现时，资源数为零的站无需等待给定时刻，应使用对应的有效门槛。单站、零预算和较大的累计时间也须正确处理。Codex（GPT-6）负责这些边界与实现说明。堆、线段树和事件批处理构成的算法为 \(O(n\log(n+1))\) 时间、\(O(n)\) 空间。

到站时间与目标函数¶

列车不能返回。若 \(\mathrm{Num}_i>0\) ，必须带走站点 \(i\) 的资源，所以离站时刻不能早于 \(T_i\) . 若 \(\mathrm{Num}_i=0\) ，该站没有待装资源，生产时刻不限制离站。令有效生产时刻 \(R_i=T_i\)（数量为正）或 \(R_i=0\)（数量为零），并令 \(R_n=0\) .

固定缩短后的行驶时间 \(D_i\) ，不必要的等待只会推迟交付，因此最优到站时刻满足

\[ A_1=0,\qquad A_{i+1}=\max(A_i,R_i)+D_i \]

站点 \(j\) 收到的资源总数为 \(W_j=\sum_{i<j}\mathrm{Num}_i\) . 总耗时是

\[ \sum_{j=1}^{n}W_jA_j-\sum_{i=1}^{n-1}(n-i)\mathrm{Num}_iT_i \]

第二项是常数。只需最小化到站时刻的加权和。定义 \(P_j=\sum_{t=1}^{j}W_t\) ，区间内交付数量之和便可用前缀和求得。

一次缩短能影响多远¶

令余量 \(S_i=A_i-R_i\) . 当 \(S_i\le0\) 时，列车已在本站等到生产完成才离开；再提前抵达，不会使它更早离开。这样的站点是到站时间变化的分界点。终点 \(n\) 也作为分界点。

若当前将第 \(i\) 段缩短 \(1\) ，它能让站点 \(i+1\) 到右侧第一个分界点 \(r\) 的到站时刻各提前 \(1\) ，包括 \(r\) 本身；超过 \(r\) 的时刻不变。收益为

\[ G(i,r)=P_r-P_i \]

即受影响的各站所交付的资源总数。所有余量和时间都是整数，所以尚未到达分界点的正余量至少为 \(1\) .

相邻分界点构成区间 \((l,r]\) . 其中各段缩短一次的右端点相同，位置越靠左，影响的站点越多，收益越大。因此只考虑区间内最靠左且仍有正行驶时间的那一段。之前行驶时间已经为零的段不再可选。

贪心为何正确¶

先证明同一区间内可以优先缩短最左侧的可用段 \(l\) . 假设某个最优剩余方案在此区间投入了操作，却没有选择 \(l\) . 令 \(j\) 是该方案在区间内选择的最左段，将它的一次操作移到 \(l\) . 移入段长度为正且原方案未缩短它，故操作合法。

原方案在 \(l\) 到 \(j-1\) 上没有任何缩短，而这些位置间所有站点的当前余量都是正整数。因此移来的这一次操作不会被中途等待抵消，能让站点 \(l+1\) 到 \(j\) 都提前 \(1\) ；经过第 \(j\) 段时，其行驶时间增加 \(1\) ，两者恰好抵消。之后的到站时刻完全不变，之前的交付只会改善。因此可以逐次交换，得到按当前最左可用段推进、在出现新分界点时重新分配的最优方案。

也可从各段的边际收益看这一过程：在已有分界点之间，最左可用段当前收益最大；每用一次后，它的收益保持不变，直到该段耗尽或区间分裂。耗尽后候选左端点右移；分裂后每个子区间只含原区间的一部分站点。因 \(W_j\ge0\) ，后续候选收益都不超过先前收益。已有分界点也不会消失，因为缩短线路只能让到站更早。

因此，每个区间的操作可以组织成收益不增的阶段，后继阶段只有完成前一阶段才可用。不同区间的到站变化互不越过分界点。对这些阶段，每次选择当前最大收益：尚未开放的阶段收益不超过其前置阶段，故不会藏有更大的可获收益。交换最优方案中的操作顺序，便可使它的下一次操作与贪心一致。重复交换，得到贪心的最优性。

按事件批量处理¶

用最大堆维护每个区间的候选段及收益。取出区间，令 \(l\) 是其最左可用段下标，\(r\) 是右分界点。在候选收益发生变化前，可连续操作

\[ \Delta=\min\left(K,D_l,\min_{l<j<r}S_j\right) \]

次。内部没有站点时，最后一项视为正无穷。

将剩余额度和 \(D_l\) 都减去 \(\Delta\) .
将 \((l,r]\) 中所有余量减去 \(\Delta\) ，这些站点的到站时刻也提前相同的量。
找出内部所有新变为零的余量，以这些站点拆分区间。
对每个子区间，略过已经耗尽的线路，重新将最左可用段放入堆。

使用支持区间加、区间最小值的线段树维护余量，并利用节点最小值剪枝寻找新分界点。另用差分数组记录各次区间提前量，最后恢复实际到站时刻，代入目标公式。

当没有正收益候选时即可结束，因为允许少用命令方块。参考程序使用从 \(0\) 开始的下标：Delivered 对应 \(W\) ，Prefix 对应 \(P\) ，Ready 对应有效生产时刻 \(R\) .

复杂度与数值范围¶

每个完整批次至少耗尽一段线路或建立一个永久分界点，另有至多一次额度耗尽。因此共有 \(O(n)\) 个批次；每个新分界点只被加入一次，每个零长度段在候选左端点向右移动时只被略过一次。线段树与堆的总时间为 \(O(n\log n)\) ，空间为 \(O(n)\) ，不依赖 \(K\) 的数值大小。\(n=1\) 时没有运输，直接由同一实现输出 \(0\) .

到站时刻、余量和区间收益使用有符号 64 位整数。完整总耗时可能超过 64 位范围，所以只在计算最终答案时分步取模；堆中的收益比较保持精确整数。先将乘法因子对 \(10^9+9\) 取模，再相乘，并规范化减法结果。用 \(R_i\) 代替公式中的 \(T_i\) 不改变生产时刻项，因为二者只可能在 \(\mathrm{Num}_i=0\) 时不同。

验证与贡献¶

4 组样例及 708 组独立穷举对拍通过。暴力枚举每一段的全部缩短量组合，在总次数约束下直接模拟资源交付，不使用分界点贪心。测试包含相同生产时刻下资源数量为零或为正的区分、空任务、零长度线路、超过总路程的额度及大数取模。

Codex（GPT-6）：负责批量贪心算法的线段树与最大堆实现、零资源站处理、模运算、边界说明及独立验证。源码见 std.cpp。