MarsCode算法题体验之--暴雨梨花针[贪心算法]

原题目:这道题结合了经典的思想，要求我们找到发射最少次数的暴雨梨花针，以覆盖给定的靶子区域。题目中，唐三只能垂直于 X 轴发射暴雨梨花针，所有靶子的左、右边界以及其纵坐标都明确给出，我们需要考虑如何用最少的攻击次数覆盖所有靶子。以下是我解题的详细思路和心得。

pray008

806人浏览 · 2024-09-24 22:54:28

pray008 · 2024-09-24 22:54:28 发布

原题目:

这道题结合了经典的贪心算法思想，要求我们找到发射最少次数的暴雨梨花针，以覆盖给定的靶子区域。题目中，唐三只能垂直于 X 轴发射暴雨梨花针，所有靶子的左、右边界以及其纵坐标都明确给出，我们需要考虑如何用最少的攻击次数覆盖所有靶子。以下是我解题的详细思路和心得。

1. 问题理解

在二维平面上，每个靶子可以视为一条线段，暴雨梨花针的发射是沿着垂直 X 轴的直线。唐三每发射一根针，可以覆盖一个范围内的多个靶子，只要这些靶子与该针在垂直方向上有重叠即可。为了节省资源，问题要求我们找出最少的发射次数。

关键点是每一根针的发射，必须尽量覆盖更多的靶子，且靶子的范围是 [x_left, x_right]。每个靶子的右端点 x_right 决定了它能被覆盖的最远位置。

2. 解题思路

这道题典型地适合用贪心算法来解决，因为我们需要在选择发射点时，优先选择覆盖范围最远的靶子。

核心步骤：

靶子的右端点排序：我们可以按照靶子的右端点 x_right 进行排序。排序后，我们从左往右遍历靶子，尽可能利用一根针覆盖尽量多的靶子。
选择发射点：每次发射一根针时，选择能够覆盖当前靶子以及尽量多后续靶子的最右位置。然后继续处理未被覆盖的靶子。
记录发射次数：每次确定一根针能覆盖的靶子范围后，记录一次发射，并继续处理下一个未被覆盖的靶子，直到所有靶子都被击中。

3. 代码实现

基于上面的思路，我实现了以下 Java 代码：

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

public class TangSanBowRain {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int K = scanner.nextInt(); // 靶子的数量
int P = scanner.nextInt(); // 取模用的参数

int[][] targets = new int[K][3];
for (int i = 0; i < K; i++) {
targets[i][0] = scanner.nextInt(); // x_left
targets[i][1] = scanner.nextInt(); // x_right
targets[i][2] = scanner.nextInt(); // y
}

// 按照靶子的右端点进行排序
Arrays.sort(targets, (a, b) -> Integer.compare(a[1], b[1]));

int arrows = 0; // 暴雨梨花针的发射次数
int lastShotPosition = -1; // 上次发射的位置

// 遍历所有靶子
for (int i = 0; i < K; i++) {
if (targets[i][0] > lastShotPosition) {
// 如果当前靶子的左端点在上次发射的范围之外，必须发射新的针
arrows++;
lastShotPosition = targets[i][1]; // 更新发射的位置为当前靶子的右端点
}
}

// 输出发射次数的结果
System.out.println(arrows % P);
}
}

4. 代码解析

输入处理：首先读取靶子的数量 K 和取模的参数 P，然后依次读取每个靶子的坐标 [x_left, x_right, y]，并存储到二维数组 targets 中。
排序：代码中使用 Arrays.sort() 按照靶子的右端点 x_right 进行升序排序，这是贪心算法的核心步骤。通过排序，可以确保每次尽量选择最左侧的靶子进行发射，同时覆盖尽量多的靶子。
发射暴雨梨花针：代码遍历每个靶子，判断当前靶子的左端点是否已经被之前的发射覆盖。如果没有覆盖到（即当前靶子的 x_left 大于上次发射的 lastShotPosition），则需要发射新的一针，并更新发射的位置为当前靶子的右端点。
输出结果：最后，输出暴雨梨花针的发射次数对 P 取模后的结果。