【华为OD-E卷 – 118 路灯照明问题 100分（python、java、c++、js、c）】

【华为OD-E卷 – 路灯照明问题 100分（python、java、c++、js、c）】

题目

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

输入描述

输出描述

用例

用例一：

输入：

2
50 50

输出：

0

用例二：

输入：

4
50 70 20 70

输出：

20

python解法

输入一个整数 n，表示有 n 盏灯。
接着输入 n 个整数 arr，其中 arr[i] 表示第 i 盏灯的照明范围（左右各 arr[i] 个单位）。
第 i 盏灯的位置在 i * 100 这个坐标点上，照明区间为 [i * 100 – arr[i], i * 100 + arr[i]]。
目标是计算从第 0 盏灯到第 n-1 盏灯的区域中未被照亮的总长度。
算法思路：

构建照明区间：根据每盏灯的位置和照明范围，构建照明区间 [start, end]。
区间排序：将所有区间按起始位置 start 进行升序排序，方便后续合并区间。
合并区间并计算未照亮长度：
从第一个区间开始，记录当前的照明结束位置 current_end。
遍历后续区间：
如果当前区间的起始位置 start 大于 current_end，说明这两个区间之间有未被照亮的部分，累加未照亮的长度。
更新 current_end 为当前区间的结束位置 end 和 current_end 中的较大值，以确保正确合并重叠区间。
返回未照亮的总长度

# 读取输入，n表示灯的数量
n = int(input())
# 读取每盏灯的照明范围，存储在arr列表中
arr = list(map(int, input().split()))

# 定义计算未被照亮长度的函数
def find_unlit_length():
    intervals = []  # 存储每盏灯的照明区间

    # 计算每盏灯的照明区间
    for i in range(n):
        start = i * 100 - arr[i]  # 照明区间的起始位置
        end = i * 100 + arr[i]    # 照明区间的结束位置
        intervals.append([start, end])  # 将区间加入列表

    intervals.sort()  # 按区间的起始位置进行排序

    total_unlit = 0  # 记录未被照亮的总长度
    current_end = intervals[0][1]  # 初始化当前照明的最远结束位置

    # 遍历后续的区间，计算未被照亮的部分
    for i in range(1, n):
        # 如果当前区间的起点在当前照明范围之外，说明有未被照亮的部分
        if intervals[i][0] > current_end:
            total_unlit += intervals[i][0] - current_end  # 累加未被照亮的长度
        
        # 更新当前照明的最远结束位置
        current_end = max(current_end, intervals[i][1])

    return total_unlit  # 返回未被照亮的总长度

# 输出结果
print(find_unlit_length())

java解法

输入一个整数 n，表示有 n 盏灯。
每盏灯的位置在 i * 100（第 i 盏灯，i 从 0 开始）。
每盏灯的照明范围由输入的 radius 决定，照明区间为 [i * 100 – radius, i * 100 + radius]。
任务是计算所有灯的照明范围内，未被照亮的总长度。
算法思路：

构建照明区间：根据每盏灯的位置和照明半径，构建对应的区间 [start, end]。
区间排序：将所有区间按 start 升序排序，如果 start 相同，则按 end 升序排序，方便后续合并区间。
合并区间并计算未覆盖长度：
从第一个区间开始，记录当前照明的结束位置 currentEnd。
遍历后续区间：
如果当前区间的 start 大于 currentEnd，说明中间有未被照亮的部分，累加未被照亮的长度。
更新 currentEnd 为当前区间的 end 和 currentEnd 中的较大值，以确保正确合并重叠区间。
返回未覆盖的总长度

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();  // 读取灯的数量
        List<Segment> segments = new ArrayList<>();  // 用于存储每盏灯的照明区间

        // 读取每盏灯的照明半径，并计算对应的照明区间
        for (int i = 0; i < n; i++) {
            int center = i * 100;  // 第 i 盏灯的位置
            int radius = scanner.nextInt();  // 读取照明半径
            // 构建照明区间 [center - radius, center + radius]
            segments.add(new Segment(center - radius, center + radius));
        }

        // 计算并输出未被照亮的总长度
        System.out.println(calculateUncoveredLength(segments));
    }

    // 计算未被照亮长度的方法
    private static int calculateUncoveredLength(List<Segment> segments) {
        // 将所有照明区间按起始位置排序，如果起始位置相同则按结束位置排序
        Collections.sort(segments, (a, b) -> a.start != b.start ? a.start - b.start : a.end - b.end);

        int uncoveredLength = 0;  // 记录未被照亮的总长度
        int currentEnd = segments.get(0).end;  // 初始化当前照明的最远结束位置

        // 遍历所有照明区间，合并重叠部分并计算未被覆盖的长度
        for (int i = 1; i < segments.size(); i++) {
            // 如果当前区间的起始位置在当前照明范围之外，说明有未被照亮的部分
            if (segments.get(i).start > currentEnd) {
                uncoveredLength += segments.get(i).start - currentEnd;  // 累加未被照亮的长度
            }
            // 更新当前照明的最远结束位置
            currentEnd = Math.max(currentEnd, segments.get(i).end);
        }

        return uncoveredLength;  // 返回未被照亮的总长度
    }

    // 定义表示照明区间的内部类
    private static class Segment {
        int start, end;

        Segment(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

C++解法

更新中

C解法

更新中

JS解法

输入两行数据：
第一行是一个整数，表示灯的数量 lampCount。
第二行是 lampCount 个整数，表示每盏灯的照明半径 radii。
每盏灯安装在位置 i * 100，其中 i 从 0 开始计数。
每盏灯的照明范围是 [i * 100 – radii[i], i * 100 + radii[i]]。
目标是计算所有灯的照明范围内，未被照亮的总长度。
算法思路：

构建照明区间：根据每盏灯的位置和照明半径，构建区间 [start, end]。
区间排序：按区间的起始位置 start 升序排序。如果起始位置相同，按结束位置 end 降序排序，确保较大的覆盖范围优先。
合并区间并计算未照亮长度：
从第一个区间开始，记录当前照明的结束位置 currentEnd。
遍历后续区间：
如果当前区间的起始位置 start 大于 currentEnd，说明两个区间之间存在未被照亮的区域，累加该未照亮的长度。
更新 currentEnd 为当前区间的结束位置 end 和 currentEnd 中的较大值，以合并重叠区间。
返回未照亮的总长度

const readline = require("readline");

// 创建读取输入的接口
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const inputData = [];  // 存储输入数据

// 监听输入，每输入一行触发一次
rl.on("line", (line) => {
  inputData.push(line.trim());  // 去掉多余空白并存入数组

  // 当输入了两行数据后，开始处理
  if (inputData.length === 2) {
    const lampCount = parseInt(inputData[0]);  // 读取灯的数量
    const radii = inputData[1].split(" ").map(Number);  // 读取每盏灯的照明半径并转换为数字数组

    console.log(findUnlitLength(lampCount, radii));  // 调用计算函数并输出未被照亮的总长度

    inputData.length = 0;  // 清空输入数据，准备下一组输入（如果有）
  }
});

// 计算未被照亮长度的函数
function findUnlitLength(lampCount, radii) {
  const coverage = [];  // 存储每盏灯的照明区间

  // 计算每盏灯的照明范围
  for (let i = 0; i < lampCount; i++) {
    const startPos = i * 100 - radii[i];  // 计算照明区间的起始位置
    const endPos = i * 100 + radii[i];    // 计算照明区间的结束位置
    coverage.push([startPos, endPos]);    // 将区间存入数组
  }

  // 按区间的起始位置升序排序，如果起始位置相同，按结束位置降序排序
  coverage.sort((a, b) => a[0] - b[0] || b[1] - a[1]);

  let totalUnlit = 0;  // 记录未被照亮的总长度
  let currentEnd = coverage[0][1];  // 初始化当前照明的最远结束位置

  // 遍历后续的区间，合并重叠部分并计算未被照亮的长度
  for (let i = 1; i < lampCount; i++) {
    const [start, end] = coverage[i];  // 当前区间的起始和结束位置

    if (start > currentEnd) {
      // 如果当前区间的起始位置在当前照明范围之外，说明有未被照亮的部分
      totalUnlit += start - currentEnd;  // 累加未被照亮的长度
      currentEnd = end;  // 更新当前照明的最远结束位置
    } else {
      // 如果当前区间与前一个区间有重叠，更新当前照明范围的结束位置
      currentEnd = Math.max(currentEnd, end);
    }
  }

  return totalUnlit;  // 返回未被照亮的总长度
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

作者：CodeClimb