算法（蓝桥杯）贪心算法4——拦截导弹的系统数量求解

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

假设某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入 n个导弹依次飞来的高度（给出的高度数据是不大于 30000的正整数），计算如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

比如：有 8 颗导弹，飞来的高度分别为

389 207 175 300 299 170 158 165

那么需要 2 个系统来拦截，他们能够拦截的导弹最优解分别是：

系统 11 ：拦截 389 207 175 170158158

系统 22 ：拦截 300 299 165

输入

两行，第一行表示飞来导弹的数量 n（n≤1000）；

第二行表示 n 颗依次飞来的导弹高度；

输出

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

样例

知识点

贪心算法

过程逻辑：

代码

python">n=int(input())
a=[int(i) for i in input().split()]
b=[0]*1010
k=0
for i in range(n):p = -1for j in range(k):if a[i]<=b[j]:p=jbreakif (p == -1):b[k] = a[i]k += 1else:b[p] = a[i]
print(k)

代码解析

这道题包含了能拦截和不能拦截两种情况，不能拦截就要加多一个系统，能拦截指的是所有的系统里面有一个能拦截就能拦截；一开始最容易想到来判断我上面说的能不能拦截的条件就是目前的导弹发射高度是否大于上一个的高度，但是这个想法是不准确的，能不能拦截这个问题是动态的，可能第一个系统不能，但是第二个系统就能了，所以仅仅通过a[i]与b[j]的大小判断来作为能不能拦截的条件是不准确的，此处引入p来作为能不能拦截的条件变量，通过循环遍历每套系统拦截的最高高度数组，判断每一个系统是否能够拦截当前导弹。

扩展

改变输出样例：

题解

（一）输入部分

Python复制
n = int(input())
a = [int(i) for i in input().split()]
n = int(input())：读取用户输入的一个整数n，表示整数序列的长度。

a = [int(i) for i in input().split()]：读取用户输入的一行数据，使用input().split()将输入的字符串按空格分割成多个子字符串，然后通过列表推导式将这些子字符串转换为整数，构成一个整数列表a。

（二）初始化部分

Python复制
b = [0] * 1010
k = 0
c = []
b = [0] * 1010：初始化一个长度为1010的列表b，用于存储当前最长递增子序列的末尾元素。1010是一个足够大的数，确保不会溢出。

k = 0：初始化一个计数器k，用于记录当前最长递增子序列的长度。

c = []：初始化一个空列表c，用于记录每个元素在最长递增子序列中的位置和值。

（三）动态规划部分

Python复制
for i in range(n):p = -1for j in range(k):if a[i] <= b[j]:p = jbreakif p == -1:b[k] = a[i]c.append([k, a[i]])k += 1else:b[p] = a[i]c.append([p, a[i]])
for i in range(n):：通过一个循环，遍历输入的整数序列a。

p = -1：初始化一个变量p为-1，用于记录当前元素a[i]在b中的插入位置。

for j in range(k):：通过一个内层循环，遍历当前最长递增子序列的末尾元素列表b。

if a[i] <= b[j]:：如果当前元素a[i]小于或等于b[j]，则找到插入位置。

p = j：将插入位置记录为j。

break：跳出内层循环。

if p == -1:：如果p仍为-1，说明当前元素a[i]可以扩展最长递增子序列。

b[k] = a[i]：将a[i]添加到b的末尾。

c.append([k, a[i]])：记录当前元素的位置和值。

k += 1：更新最长递增子序列的长度。

else:：如果p不为-1，说明当前元素a[i]可以替换b中的某个元素。

b[p] = a[i]：将b[p]更新为a[i]。

c.append([p, a[i]])：记录当前元素的位置和值。

（四）排序与分组部分

Python复制
# 按照第二个元素排序
array = sorted(c, key=lambda x: x[0])
# 初始化一个字典用于存储分类后的数据
data_dict = {}
# 遍历排序后的数组
# 遍历数组，根据第一个元素进行分组
for item in array:key = item[0] + 1  # 将第一个元素加1作为字典的键value = item[1]    # 第二个元素作为值if key in data_dict:data_dict[key].append(value)else:data_dict[key] = [value]
array = sorted(c, key=lambda x: x[0])：按照每个子列表的第一个元素（即位置）对列表c进行排序。

data_dict = {}：初始化一个字典data_dict，用于存储分类后的数据。

for item in array:：遍历排序后的列表array。

key = item[0] + 1：将每个子列表的第一个元素加1作为字典的键。

value = item[1]：将每个子列表的第二个元素作为值。

if key in data_dict:：如果键已经存在于字典中，将值添加到对应的列表中。

else:：如果键不存在于字典中，创建一个新的列表并添加值。

（五）输出部分

Python复制
# 按照指定的格式输出
print(k)
for key, values in data_dict.items():print(f"{key}:{' '.join(map(str, values))}")
print(k)：输出最长递增子序列的长度。

for key, values in data_dict.items():：遍历字典data_dict。print(f"{key}:{' '.join(map(str, values))}")：按照指定的格式输出每个位置上的元素。其中，map(str, values)将值列表中的每个元素转换为字符串，' '.join(...)将这些字符串用空格连接起来。

完整代码

python">n=int(input())
a=[int(i) for i in input().split()]
b=[0]*1010
k=0
c=[]
for i in range(n):p = -1for j in range(k):if a[i]<=b[j]:p=jbreakif (p == -1):b[k] = a[i]c.append([k,a[i]])k += 1else:b[p] = a[i]c.append([p,a[i]])
# 按照第二个元素排序
array = sorted(c, key=lambda x: x[0])
# 初始化一个字典用于存储分类后的数据
data_dict = {}
# 遍历排序后的数组
# 遍历数组，根据第一个元素进行分组
for item in array:key = item[0] + 1  # 将第一个元素加1作为字典的键value = item[1]    # 第二个元素作为值if key in data_dict:data_dict[key].append(value)else:data_dict[key] = [value]
# 按照指定的格式输出
print(k)
for key, values in data_dict.items():print(f"{key}:{' '.join(map(str, values))}")