P3101. 路灯照明问题

解题思路

这也是一个典型的区间类贪心问题，和题目【贪心】2024E-会议室占用时间 非常类似。

数据预处理

首先我们需要把所给的照明半径的数据转化为方便我们处理的区间格式。以示例二为例，如图所示。

很容易看到，每一个路灯的照明区间，是由其自身的位置和其照明半径确定的。对于索引为 i 的路灯，其位置为 100*i（路灯间隔固定为100），若其照明半径为 r，其照明区间容易计算得到 [100*i - r, 100*i + r]。

故对于长度为 n 的照明半径数组 rads，我们可以直接使用推导式构建得到每一个路灯对应的照明区间数组 intervals。代码为：

这就完成了对区间的数据预处理工作。

区间贪心问题的解决

题目要求计算的是不能够照明得到的总距离。

容易发现这个问题和【贪心】2024E-会议室占用时间 非常类似。

在前一道题中，题目要求计算的是所有重叠区间合并后的结果，而本题要求计算的是所有重叠区间合并后，合并区间之间剩余的间隔总和。

因此两道题目的核心算法逻辑是一致的，唯一区别的地方是更新答案的写法有所不同。

我们只需要将前一题中的核心计算过程：

修改为：

换言之，在遍历所有区间的过程中，我们仍然要讨论上一个区间的结束位置 `pre_end` 和当前区间 `[start, end]` 的关系。当：

• 上一个区间的结束位置 `pre_end` 小于当前区间的开始位置 `start` 时，我们需要更新 ans，令其增加 start - pre_end 的距离作为新增加的无法照明得到的距离，同时令 pre_end 更新为 end，作为后续区间的上一个区间结束位置。
• 上一个区间的结束位置 `pre_end` 大于等于当前区间的开始位置 `start` 时，两个区间之间没有空隙，这两个区间可以直接进行合并，合并后新的区间的结束位置为 pre_end 和 end 之间的较大值。

复杂度分析

• 设路灯个数为 n。构建 intervals 数组是一次遍历，O(n)；瓶颈在按区间起点排序这一步，O(n log n)；之后合并区间只有一个顺序遍历的 for 循环，每个区间恰好被处理一次，每次只做常数次比较和更新，O(n)。整体时间复杂度为 O(n log n)。
• 说明一下为什么排序不能省：区间起点是 i*100 - rads[i]，当某盏灯的照明半径很大时，它的区间起点可能比前一盏灯的更靠左，intervals 并不天然按起点有序，所以必须先排序再做单遍合并。
• 空间上需要 intervals 数组存 n 个区间，为 O(n)；合并过程本身只用 ans 和 pre_end 两个变量，额外辅助空间 O(1)。