职业进阶 题解

思路

薪资不下降，因此一旦决定晋升，就应在当前职位只赚到刚好足够支付课程的金额；多赚的钱可保留到后续。枚举最终停止晋升的位置即可。

做法

子任务 1：相同收入

所有职位收入相同时，晋升只会额外消耗金钱和天数，不可能更优，答案为 $\lceil c/a_1\rceil$。

子任务 2：状态最短路

把金钱截断到 $c$，状态为“职位、当前金钱”。工作或晋升均耗时一天，对这个无权图做 BFS，首次到达金钱 $c$ 即为答案。

子任务 3：线性枚举

维护到达职位 $i$ 时已经用掉的天数 days 和剩余金钱 money。先用当前薪资计算若不再晋升的完成时间并更新答案。若继续晋升，则补赚到至少 $b_i$，用一天支付并晋升，再进入下一职位。

复杂度

相同收入支线为 $O(1)$；状态最短路为 $O(nc)$；满分算法为 $O(n)$。满分算法空间复杂度为 $O(1)$。

正确性证明

引理 1　在固定要从职位 $i$ 晋升的前提下，只赚到首次足以支付 $b_i$ 的时刻再晋升最优。

证明　更早无法晋升；更晚赚取的额外金钱也可在薪资不低的后续职位赚到，延迟不会带来优势。∎

引理 2　线性维护值是到达每个职位时的最早天数及该最早方案的剩余金钱。

证明　由引理 1，每次晋升前的补赚天数唯一取最小；支付课程后保留全部余额，归纳成立。∎

定理　算法输出购买电脑的最少天数。

证明　任何方案都有一个最高到达职位。算法枚举了每个该位置，并由引理 2 以最早状态到达，再计算在此工作至 $c$ 的最短时间，因此取最小覆盖全部最优方案。∎