P17795 [入门赛 #53] 新能源之旅 题解

· · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

先考虑容量已经确定的情况。每次电量不足时必须换电，但电量还够时是否值得提前换电？我们可以一直使用初始电池，直到它无法通过下一段道路，再考虑备用电池。要说明这样不会错过更好的方案，可以把备用电池负责的道路看成若干连续区间：每块备用电池不能充电，所以它负责的区间内，所有消耗之和都不能超过容量 C。

设初始电池最多能独自通过前 p 段道路。任何可行方案都必须在第 p+1 段道路开始前或更早使用备用电池。把这个方案第一次换电的位置推迟到第 p+1 段道路之前，相当于从备用电池原来负责的道路中删去一段前缀。删去的道路改由初始电池完成；剩下的每个区间消耗不会增加，所需备用电池数量也不会增加。因此，初始电池尽量用到不能继续，是一种不会丢失可行方案的选择。如果它已经通过全部道路，就不需要备用电池。

换上备用电池后，同样应该尽量走远。假设某个方案让当前这块电池只走到较早的位置，我们把它的使用范围延长到仍能通过的最远位置，就又从后续电池负责的道路中删去了一段前缀，不会增加后续所需电池数。逐块应用这个理由，便得到完整的贪心策略：当前电量能够通过下一段道路就继续使用，不够时才换电。这个策略使用的备用电池数量最少，因此可以用来判断容量是否可行。

模拟时维护剩余电量 e 和已使用的备用电池数 used。若 a_i>C，任何电池都无法通过这一段，立即返回不可行；否则，若 e<a_i，就消耗一块备用电池并把电量重置为 C，超过 K 块则返回不可行。接着扣除 a_i，并且仅在 used=0 时进行充电，将电量更新为 \min(C,e+b_i)。这样就同时落实了先行驶后充电、容量截断以及备用电池不能充电的规则。

接下来寻找最小的可行容量。若某个容量已经可行，把容量增大后，保持原方案的换电位置即可：初始和换电后的电量不会减少，经过相同消耗与充电后电量也不会更少。可行性具有单调性，可以二分答案。每段道路都必须完整地由一块电池通过，所以二分下界取 \max a_i；上界取 \sum a_i，因为这么大的初始电池即使完全不充电，也足以完成全程。每次用前面的贪心模拟判定，就能找到最小可行容量。