题解

思路

已铺防护布的左端严格递增，而且所有防护布等长，所以相邻两块之间尚未覆盖的长度为 $\max(0,a_i-(a_{i-1}+W))$；桥左端的空隙长为 $a_1$，右端的空隙长为 $L-(a_N+W)$。

做法

一块新增防护布最多为某段空隙贡献长度 $W$，因此覆盖长度为 $d$ 的空隙至少需要 $\lceil d/W\rceil$ 块。反过来，从空隙左端起连续铺设这些防护布一定可以覆盖它，末块即使越过空隙边界也只会与已有防护布重叠，故这个下界能够达到。把所有空隙的答案相加即可。

扫描一次数组并用整数式 $(d+W-1)/W$ 计算上取整。所有长度和答案都应使用 64 位整数。

复杂度

时间复杂度为 $O(N)$，除输入数组外只需 $O(1)$ 额外空间。