Java 导弹拦截系统问题：贪心算法求解最少系统数

问题描述：

某国为了防御敌国的导弹袭击，开发出了一种导弹拦截系统，但该系统存在一个缺陷：虽然第一发炮弹能够到达任意的高度，但之后每一发炮弹都不能高于前一发的高度。现已知敌国导弹来袭的高度，请计算要拦截所有导弹至少需要配备多少套该系统。

输入：

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

输出：

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

思路：

使用贪心算法，维护一个递增的序列。每次遍历到一个新的导弹高度，若比当前序列中最高的高度还高，则需要新配备一套系统；否则在序列中找到第一个比该导弹高度高的位置，将其替换成该导弹高度。

代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> heights = new ArrayList<>();
        while (sc.hasNextInt()) {
            int h = sc.nextInt();
            int idx = Collections.binarySearch(heights, h);
            if (idx < 0) {
                idx = -idx - 1;
                if (idx == heights.size()) {
                    heights.add(h);
                } else {
                    heights.set(idx, h);
                }
            }
        }
        System.out.println(heights.size());
    }
}

代码解释：

使用 Scanner 类读取输入的导弹高度，并将它们存储在 heights 列表中。
使用 Collections.binarySearch 方法在 heights 列表中查找第一个大于等于当前导弹高度的位置。
若 idx 为负数，则说明 heights 列表中没有大于等于当前导弹高度的值，需要新配备一套系统，并将该导弹高度添加到 heights 列表的末尾或合适位置。
若 idx 为非负数，则说明 heights 列表中存在大于等于当前导弹高度的值，需要将该值替换为当前导弹高度，以便维护 heights 列表的递增性。
最终 heights 列表的长度即为所需的最少系统数量。

总结：

本文介绍了使用 Java 语言解决导弹拦截系统问题的方案，该方案基于贪心算法，能够高效地计算出拦截所有导弹所需的最少系统数量。通过代码示例和详细解释，帮助读者更好地理解贪心算法的应用场景和实现方法。