本文共 1020 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要计算最少需要配备多少套导弹拦截系统。每套系统发射的炮弹高度必须是递减的。因此，我们可以将其转化为寻找最长递减子序列的问题，以确定最少需要的系统数。

方法思路

为了找到最少需要的导弹拦截系统数量，我们可以将其转化为寻找最长递增子序列的问题。每个递增子序列对应一个系统，这样系统数越少，越能覆盖更多的导弹。

具体步骤如下：

解决代码

import bisect
def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    while ptr < len(input):
        n = int(input[ptr])
        ptr += 1
        a = list(map(int, input[ptr:ptr + n]))
        ptr += n
        tails = []
        for x in a:
            idx = bisect.bisect_right(tails, x)
            if idx == 0:
                tails.insert(0, x)
            else:
                tails[idx] = x
        print(len(tails))
if __name__ == "__main__":
    main()

代码解释

这种方法利用了二分查找优化，最长递增子序列的时间复杂度为 O(n log n)，适用于较大的数据规模。