华为OD机试_2025 B卷_路灯照明问题（Python，100分）（附详细解题思路）

题目描述

在一条笔直的公路上安装了N个路灯，从位置0开始安装，路灯之间间距固定为100米。
每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，无法照明的区间的长度和。

输入描述
第一行为一个数N，表示路灯个数，1<=N<=100000
第二行为N个空格分隔的数，表示路灯的照明半径，1<=照明半径<=100000*100

输出描述
第一个路灯和最后一个路灯之间，无法照明的区间的长度和

用例

路灯照明问题：区间合并的巧妙应用

核心解题思路

在笔直的公路上安装N个路灯，间距固定100米，每个路灯有自己的照明半径。我们需要计算第一个路灯（位置0）和最后一个路灯（位置(N-1)*100）之间未被照明的区间总长度。

解决问题的关键在于区间合并：

1. 计算每个路灯的实际照明区间（考虑边界限制）
2. 合并所有重叠的照明区间
3. 计算合并后区间之间的空隙总和

为什么使用区间合并？

• 路灯照明范围可能相互重叠
• 多个路灯可能形成连续照明区域
• 未照明区域只存在于照明区间之间的空隙

完整解题过程

步骤1：理解路灯照明范围

对于第i个路灯（位置为i*100）：

• 理论照明范围：[i*100 - 半径, i*100 + 半径]
• 实际有效范围（在[0, (N-1)*100]区间内）：

  left = max(0, i*100 - radius)
  right = min((N-1)*100, i*100 + radius)
  

步骤2：区间合并算法

1. 收集所有照明区间
2. 按左端点排序
3. 合并重叠区间：
   • 如果新区间左端点 ≤ 当前右端点，合并区间
   • 否则，保存当前区间，开始新区间

步骤3：计算未照明区域

1. 总路段长度：(N-1)*100
2. 计算所有合并后照明区间总长度
3. 未照明长度 = 总长度 - 照明总长度

代码实现

def main():
    # 读取路灯数量
    n = int(input().strip())
    
    # 读取照明半径
    radii = list(map(int, input().split()))
    
    # 计算总路段长度
    total_length = (n - 1) * 100
    
    # 处理特殊情况：只有一个路灯
    if n == 1:
        print(0)
        return
    
    # 计算每个路灯的有效照明区间
    intervals = []
    for i in range(n):
        pos = i * 100
        left = max(0, pos - radii[i])
        right = min(total_length, pos + radii[i])
        intervals.append((left, right))
    
    # 按左端点排序
    intervals.sort(key=lambda x: x[0])
    
    # 合并重叠区间
    merged = []
    current_start, current_end = intervals[0]
    
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        # 检查是否与当前区间重叠
        if start <= current_end:
            # 合并区间
            current_end = max(current_end, end)
        else:
            # 保存当前合并区间
            merged.append((current_start, current_end))
            # 开始新区间
            current_start, current_end = start, end
    
    # 添加最后一个区间
    merged.append((current_start, current_end))
    
    # 计算照明总长度
    covered_length = 0
    for interval in merged:
        covered_length += (interval[1] - interval[0])
    
    # 计算未照明长度
    uncovered_length = total_length - covered_length
    print(uncovered_length)

if __name__ == "__main__":
    main()

实例解析（输入4，半径[50,70,20,70]）

路灯位置和有效照明范围：

区间合并过程：

1. 排序后区间：[0,50], [30,170], [180,220], [230,300]
2. 合并：
   • [0,50]和[30,170] → 合并为[0,170]
   • [180,220]独立
   • [230,300]独立
3. 合并后区间：[0,170], [180,220], [230,300]

长度计算：

• 总路段长度：300
• 照明总长度：(170-0) + (220-180) + (300-230) = 170+40+70=280
• 未照明长度：300-280=20

关键点说明

1. 边界处理：

   • 使用max(0, ...)确保左边界≥0
   • 使用min((N-1)*100, ...)确保右边界不超过路段终点

2. 区间合并核心逻辑：

   if intervals[i][0] <= current_end:
       current_end = max(current_end, intervals[i][1])
   else:
       merged.append((current_start, current_end))
       current_start, current_end = intervals[i]
   

3. 特殊情况处理：

   • 单个路灯时未照明区域为0
   • 全路段照明时输出0

扩展思考

实际应用场景

1. 无线基站信号覆盖优化
2. 安防监控摄像头布局
3. 农业灌溉系统设计
4. 城市路灯节能规划

算法变体

1. 实时区间更新：动态添加/删除照明源
2. 多维空间扩展：将算法应用于二维平面
3. 概率模型：考虑照明强度衰减模型
4. 并行计算：使用分治法加速大规模数据处理

通过区间合并算法，我们高效解决了路灯照明问题。这种思路不仅适用于本题，还能扩展到各种资源覆盖优化场景。掌握核心算法思想，就能举一反三解决实际问题！