题目名称

小红的物资调度

问题描述

题解

分析题意后发现，要从起点到终点，最终会买 $n - 1$ 个单位的物质，那么我只需要判断，当前从 $i$ 到 $i + 1$ 这一步转移所需要的物资从哪个城邦买即可。

做法

​ 维护一个单调队列 $queue$，其中购买物资的价格依次上升。

​ 假设当前要从第 $i$ 个城邦走到第 $i + 1$ 个城邦，并且打算从第 $j$ 个城邦买当前转移的所需的物资（单位1），那么此时的花费为 $i - j + cost[j]$，如果此时从第 $j$ 买物资花费要大于 $cost[i]$ （即从第 $i$ 个城邦买单位 $1$ 的物资），那么对于所有的 $k \in [i, n - 1]$，要从第 $k$ 个 城邦走到第 $k + 1$ 个城邦所购买的物资一定是从 $i$ 购买要优于从 $j$，那么此时的 $j$ 对后面所有城邦都不会造成贡献了，此时直接在队列中删去即可。