【python】拦截导弹

题目：

某国为了防御敌国的导弹袭击，发明出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入格式：

• 一组测试数据，包含一系列整数。
• 每个整数代表雷达捕捉到的导弹依次飞来的高度。
• 高度数据是不大于 30000 的正整数。

输出格式：

• 第一行输出单套导弹拦截系统最多能拦截多少导弹。
• 第二行输出要拦截所有导弹最少需要配备多少套导弹拦截系统。

示例和解释：

输入：

389 207 155 300 299 170 158 65

输出：

6
2

输入的序列是导弹的高度：
389 207 155 300 299 170 158 65

拦截最多导弹数量（第一行输出为 6）：
- 从第一个高度开始，我们可以拦截 389，然后是 207，因为它比 389 低。
- 然后我们可以拦截 `155`，因为它比207低。
- 但是，我们不能拦截接下来的300，因为它比155高，所以我们跳过300和299，因为299也比55高。
- 接下来我们可以拦截170，因为它比155低。
- 然后是158，因为它比170低。
- 最后是65，因为它是序列中的最小数。
- 因此，最长的非递增子序列是389, 207, 155, 170, 158, 65，所以单套系统最多能拦截的导弹数量是 6。

拦截所有导弹的最少系统数量（第二行输出为 2）：
- 第一套系统如前面所述，可以拦截 389, 207, 155, 170, 158, 65。
- 第二套系统将拦截剩余的导弹，即 300, 299。

因此，给定的输入导弹高度序列可以由两套系统全部拦截，其中第一套系统可以拦截最多 6 枚导弹。

代码：

# 最长不上升子序列（LNIS）和贪心算法
def min_interception_systems(missile_heights):
    # 动态规划数组，用于存储单个系统最多能拦截的导弹数量
    dp = [1] * len(missile_heights)  # 初始化动态规划数组，每个元素代表以该高度结束的最长不上升子序列的长度，初始为1
 
    # 计算每个导弹高度的最长不上升子序列长度
    for i in range(len(missile_heights)):  # 遍历所有导弹
        for j in range(i):  # 对于每个导弹，遍历它前面的所有导弹
            if missile_heights[j] >= missile_heights[i]:  # 如果前面的导弹高度不低于当前导弹
                dp[i] = max(dp[i], dp[j] + 1)  # 更新当前导弹的最长不上升子序列的长度
 
    # 单个系统最多能拦截的导弹数量
    max_intercepted = max(dp)  # 找到所有导弹中，最长不上升子序列的长度
 
    # 贪心算法
    # 使用最长减少子序列算法来确定最少系统套数
    # tails数组用于保存最长减少子序列的末尾元素
    tails = []  # 初始化tails数组，用于存储各个不上升子序列的最小末尾元素
 
    for height in missile_heights:  # 遍历每个导弹高度
        # 使用二分查找找到tails中第一个小于等于当前高度的元素位置
        # next函数会返回第一个满足条件的元素的索引，如果没有满足条件的元素，就返回None。
        pos = next((i for i, x in enumerate(tails) if x >= height),
                   None)  # 查找位置替换或者添加新的子序列末尾元素
 
        # 如果找到了，用当前高度替换它（保持tails非递增）
        if pos is not None:  # 如果在tails中找到了可以插入的位置
            tails[pos] = height  # 则替换该位置的元素
        else:
            # 否则，将当前高度添加到tails中，因为它开启了一个新的序列
            tails.append(height)  # 如果没有找到可以插入的位置，则在tails末尾添加一个新元素
 
    # 最少需要的系统套数
    min_systems = len(tails)  # 最少需要的拦截系统套数，即tails数组的长度
 
    return max_intercepted, min_systems  # 返回单个系统最多能拦截的导弹数量和最少需要的拦截系统套数
 
 
# 示例代码，用于测试上述函数
missile_heights_example = list(map(int, input().split()))  # 从用户输入中获取导弹高度列表
 
# 计算单个系统最多能拦截的导弹数量和最少需要的拦截系统套数
max_intercepted, min_systems = min_interception_systems(
    missile_heights_example)
print(max_intercepted)  # 打印单个系统最多能拦截的导弹数量
print(min_systems)  # 打印最少需要的拦截系统套数