# 坐地铁 — 题解

## 解法比较

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

实现时，资源数为零的站无需等待给定时刻，应使用对应的有效门槛。单站、零预算和较大的累计时间也须正确处理。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)$$

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

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

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

当没有正收益候选时即可结束，因为允许少用命令方块。参考程序使用从 $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](std.cpp)。