Java 贪心算法解决导弹拦截问题

使用 Java 贪心算法解决导弹拦截问题

问题描述:

某国为了防御敌国的导弹袭击，开发出了一种导弹拦截系统。该系统有一个缺陷：虽然第一发炮弹能够到达任意的高度，但后续每一发炮弹都不能高于前一发的高度。现在雷达捕捉到敌国导弹来袭，你需要计算拦截所有导弹所需的最小拦截系统数量。

输入:

输入为 n 颗依次飞来的导弹高度 (1 <= n <= 1000)，每个高度为不大于 30000 的正整数。

输出:

输出为要拦截所有导弹最小配备的系统数 k。

算法思路:

这道题可以采用贪心算法。具体思路是：从第一个导弹开始，每次发现当前导弹高度大于前一发导弹高度时，就新建一套拦截系统，将当前导弹高度加入到该系统中。如果当前导弹高度小于等于前一发导弹高度，则找到第一套系统中高度最接近当前导弹高度的拦截系统，将当前导弹高度加入到该系统中。

代码实现:

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

public class MissileIntercept {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 导弹数量
        List<Integer> heights = new ArrayList<>(); // 存储所有导弹高度
        for (int i = 0; i < n; i++) {
            heights.add(scanner.nextInt());
        }
        int k = getMinimumSystems(heights); // 计算最小系统数量
        System.out.println(k);
    }

    // 计算最小拦截系统数量
    public static int getMinimumSystems(List<Integer> heights) {
        List<List<Integer>> systems = new ArrayList<>(); // 存储所有拦截系统
        systems.add(new ArrayList<>()); // 初始化第一个系统
        systems.get(0).add(heights.get(0)); // 将第一个导弹加入第一个系统

        for (int i = 1; i < heights.size(); i++) {
            int currentHeight = heights.get(i);
            boolean foundSystem = false; // 是否找到合适的系统

            // 寻找可以拦截当前导弹的系统
            for (int j = 0; j < systems.size(); j++) {
                if (currentHeight <= systems.get(j).get(systems.get(j).size() - 1)) { // 如果当前导弹高度小于等于该系统的最后一个导弹高度
                    systems.get(j).add(currentHeight); // 将当前导弹加入该系统
                    foundSystem = true;
                    break;
                }
            }

            // 如果没有找到合适的系统，新建一个系统
            if (!foundSystem) {
                systems.add(new ArrayList<>());
                systems.get(systems.size() - 1).add(currentHeight);
            }
        }

        return systems.size(); // 返回最小系统数量
    }
}

代码解释:

使用 ArrayList 存储所有拦截系统，每个拦截系统也是一个 ArrayList，存储该系统中的导弹高度。
初始化第一个拦截系统，并将第一个导弹加入到该系统中。
从第二个导弹开始遍历，对于每个导弹：
- 遍历所有已存在的拦截系统，如果当前导弹高度小于等于该系统最后一个导弹的高度，则将当前导弹加入该系统。
- 如果没有找到合适的系统，则新建一个系统，并将当前导弹加入到该系统中。
最后返回拦截系统的数量。

示例:

输入：

输出：

说明:

需要两个拦截系统才能拦截所有导弹。第一个系统拦截高度为 3, 2, 4 的导弹，第二个系统拦截高度为 5, 6 的导弹。