|
|
发表于 2021-5-21 21:35:18
|
显示全部楼层
本题有两个问题，先看第一问。
问题一：这套系统最多能拦截多少导弹？
假设拦截的导弹高度为h1，h2，h3,...hk,他们需要满足的关系是h1=h2>=h3>=...>=hk
这是最长不少升子序列。
问题二：要拦截所有导弹最少要配备多少套这种导弹拦截系统
假设目前有m套拦截系统，能够拦截的导弹最高的高度为h1,h2,h3...hk
现在有一枚导弹高度为H
如果m套系统都能拦截，那么选择哪一套系统呢？
选择能够拦截H且拦截高度最小的拦截系统去拦截，把拦截高度高的留着拦截更高的导弹
这就是贪心的方法
因此，可以使用数组s表示每套拦截系统的高度
如果所有拦截系统都不能拦截，拦截系统就增加一套... |
|
发表于 2021-5-17 09:02:31
置顶卡