(B卷,100分)- 路灯照明问题（Java & JS & Python & C）

题目描述

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

输入描述

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

输出描述

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

用例

题目解析

本题可以转化为区间问题。

每个路灯的位置都是确定，假设路灯的索引为 i，那么其位置就是 i * 100。

根据第二行输入的路灯的照明半径数组arr，我们可以基于路灯的位置，求得路灯的照明范围区间

假设center = i * 100，r = arr[i]，那么照明范围区间即为：[center – r, center + r]

这样的话，我们就得到了一组区间。

接下来，我们就需要将这些区间进行合并，合并后，求剩余没有交集的区间的间隙之和就是题解。

这里区间合并是有技巧的，我们一般：

• 先将区间按照起始位置进行升序
• 如果起始位置相同，则再按照结束位置降序

这样排序的好处是，所有区间都按照起始位置升序排序了，比如第一个ran[0]和第二个区间ran[1]，我们可以确定：ran[0].start <= ran[1].start

由于这两个区间的起始位置关系已经确定了，判断这两个区间是否有交集，只要看ran[0].end和ran[1].start即可，如果ran[0].end > ran[1].start，则说明这两个区间有交集，可以合并。

另外，如果ran[0]和ran[1]的起始位置相同的话，则上面排序还会按照结束位置进行降序，即必然ran[0].end >= ran[1].end。

这样排序的好处是，后面区间的结束位置小于前面区间的结束位置时，可以直接放心并入前面区间，而不需要再进行起始位置相同的两个区间的结束位置比较。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const n = lines[0] - 0;
    const arr = lines[1].split(" ").map(Number);

    console.log(getResult(n, arr));

    lines.length = 0;
  }
});

function getResult(n, arr) {
  const ranges = [];

  for (let i = 0; i < n; i++) {
    const center = i * 100;
    ranges.push([center - arr[i], center + arr[i]]);
  }

  // 按起始位置升序，起始位置相同，则继续按结束位置降序
  ranges.sort((a, b) => (a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]));

  let ans = 0;

  let t = ranges[0][1]; // 上一个区间的结束位置
  for (let i = 1; i < n; i++) {
    const [s, e] = ranges[i]; // 当前区间的【开始位置，结束位置】

    // 有交集
    if (t >= s) {
      // 合并后的新区间将变为下一轮的上一个区间，t为新区间的结束位置
      t = Math.max(e, t);
    } else {
      // 没有交集，则统计区间间隙 s - t
      ans += s - t;
      // 当前区间变为下一轮的上一个区间，更新t
      t = e;
    }
  }

  return ans;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

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

    int n = sc.nextInt();

    int[][] ranges = new int[n][2];
    for (int i = 0; i < n; i++) {
      int center = i * 100;
      int r = sc.nextInt();
      ranges[i][0] = center - r;
      ranges[i][1] = center + r;
    }

    System.out.println(getResult(n, ranges));
  }

  public static int getResult(int n, int[][] ranges) {
    int ans = 0;

    // 按起始位置升序，起始位置相同，则继续按结束位置降序
    Arrays.sort(ranges, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);

    int t = ranges[0][1]; // 上一个区间的结束位置

    for (int i = 1; i < n; i++) {
      // 当前区间的【开始位置，结束位置】
      int s = ranges[i][0];
      int e = ranges[i][1];

      // 有交集
      if (t >= s) {
        // 合并后的新区间将变为下一轮的上一个区间，t为新区间的结束位置
        t = Math.max(e, t);
      } else {
        // 没有交集，则统计区间间隙 s - t
        ans += s - t;
        // 当前区间变为下一轮的上一个区间，更新t
        t = e;
      }
    }

    return ans;
  }
}

Python算法源码

# 输入获取
n = int(input())
arr = list(map(int, input().split()))


# 算法入口
def getResult():
    rans = []

    for i in range(n):
        center = i * 100
        rans.append([center - arr[i], center + arr[i]])

    # 按起始位置升序，起始位置相同，则继续按结束位置降序
    rans.sort(key=lambda ran: (ran[0], -ran[1]))

    ans = 0

    t = rans[0][1]  # 上一个区间的结束位置
    for i in range(1, n):
        s, e = rans[i]  # 当前区间的【开始位置，结束位置】

        # 有交集
        if t >= s:
            # 合并后的新区间将变为下一轮的上一个区间，t为新区间的结束位置
            t = max(e, t)
        else:
            # 没有交集，则统计区间间隙 s - t
            ans += s - t
            #  当前区间变为下一轮的上一个区间，更新t
            t = e

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX(a,b) (a) > (b) ? (a) : (b)

int getResult(int n, int ranges[][2]);
int cmp(const void* a, const void* b);

int main() {
    int n;
    scanf("%d", &n);

    int ranges[n][2];
    for(int i=0; i<n; i++) {
        int center = i * 100;

        int r;
        scanf("%d", &r);

        ranges[i][0] = center - r;
        ranges[i][1] = center + r;
    }

    printf("%dn", getResult(n, ranges));

    return 0;
}

int getResult(int n, int ranges[][2]) {
    int ans = 0;

    // 按起始位置升序，起始位置相同，则继续按结束位置降序
    qsort(ranges, n, sizeof(int*), cmp);

    int t = ranges[0][1]; // 上一个区间的结束位置

    for(int i=1; i<n; i++) {
        // 当前区间的【开始位置，结束位置】
        int s = ranges[i][0];
        int e = ranges[i][1];

        if(t >= s) {
            // 有交集
            // 合并后的新区间将变为下一轮的上一个区间，t为新区间的结束位置
            t = MAX(e, t);
        } else {
            // 没有交集，则统计区间间隙 s - t
            ans += s - t;
            // 当前区间变为下一轮的上一个区间，更新t
            t = e;
        }
    }

    return ans;
}

int cmp(const void* a, const void* b) {
    int* A = (int*) a;
    int* B = (int*) b;
    return A[0] != B[0] ? A[0] - B[0] : B[1] - A[1];
}