一个算法问题，我已经困惑了多时，清高手赐教（100分）(100分)

J

jxyghm

Unregistered / Unconfirmed
GUEST, unregistred user!
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种系统有一个缺陷：
虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹都不能高于前一发的
高度，某天雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，所以只有一套系统
有可能不能拦截所有导弹。
输入导弹依次飞来的高度（雷达给出不大于30000的正整数），计算这套系统
最多能够拦截多少导弹，如果要拦截所有导弹需要配多少套这种拦截系统。
样例：input
389 207 155 300 299 170 158 65
output
6(最多能拦截导弹数)
2（要拦截所有导弹需要配备的系统数）
要求，算法要清晰完整。
 
照你的说法上面的结果应该是：
input
389 207 155 300 299 170 158 65
output
8(最多能拦截导弹数)
2（要拦截所有导弹需要配备的系统数）
389 207 155 和 300 299 170 158 65 两组不是刚好都为减函数组合吗？
 
提示：用二叉树做
依次检查，如果后面的数小于前面的,则加前面数的左子，若大于，则向上搜索仅大于后面数的节点加为其右子，如果找到的节点已有右子......(说起来好麻烦，不过你应该知道怎么做了，就是从这个右子往下加)
最后生成的树一定是父节点大于左右子，这似乎叫完全二叉树。
其最大深度表示能拦截导弹数
其所有分支表示需要的拦截系统
想的时间很短，可能会有漏洞....你再多考虑一下吧！
 
timerri,谢谢，我先想象。
说一下389 207 155 300 299 170 158 65 只是样例，还可以是
65 389 100 207 400 100 50 30 29 28 27 1 70
 
敌人的导弹是同时打过来的吗？你怎么可以用后面导弹高度来判断前面一发拦截导弹
该不该打？？
 
当然是依次打过来的。
 
比方说你第一个例子
攻击导弹发射的高度：　　389 207 155 300 299 170 158 65
拦截导弹发射的高度：　　389 207 155 155 155 155 155 65 可是不对
当然如果我早就都知道了　389 不打不打300 299 170 158 65
正好符合你的答案？到底是怎么回事？
 
已经知道炮弹打来的高度，我要用我这套有缺陷的系统拦截
看我最多打下多少来。
 
第一时间知道所有炮弹打来的高度？
 
样例：input
389 207 155 300 299 170 158 65
output
6(最多能拦截导弹数)
2（要拦截所有导弹需要配备的系统数）

老大样例有问题
input
389 207 155 300 299 170 158 65
output
8(最多能拦截导弹数)
2（要拦截所有导弹需要配备的系统数）
1:389 207 155 65
2:300 299 170 158
觉得timerri老大的方法可行。
想法：
1。拦截系统多套但输入雷达参数时有一套计算机（网络）系统控制。
2。因为导弹是依次飞来。所以假设第N枚导弹飞来时，拦截系统已经处理了第N-1枚导弹，
此时无法预计系统个数，如下例子：input 100 200 300 400 500
需要5套系统。此时无需二叉树用一动态一维数组，先建它的size为1,将第一个值输入，
以后依次比较，如大于则数组的长的加一，如小于则用下一个比较。最后数组的长度就是
系统的套数。如需计算每套能打下的导弹数就建一个二维数组，加一项代表导弹数。
3。如导弹的高度全部知道，那就如下做：按降序排序，需要一套。

 
样例没错，只是问题没有说清楚，我想应该是在只有一套系统的情况下最多可以打下
多少枚导弹，并且导弹是依次飞来，高度是预测出导弹到达射程内时的高度。所以只
有按先后顺序打，不可以先挑后面高的打（否则只要一套就够了）。
这个问题可以简化成： 在一个序列中解出其最长的降序序列（未必连续，但要保证
先后顺序不变）
譬如 389 207 155 300 299 170 158 65
中最长的降序序列 是 389 300 299 170 158 65 共六个数字
 
to jxyghm:
已经知道炮弹打来的高度，我要用我这套有缺陷的系统拦截
看我最多打下多少来。
既然这样就比较简单了，可惜talk_me老兄已经解释得很清楚了．
只不过按他的思路找不到一套系统最多能打下多少个导弹，
因为最多能拦截导弹数　很可能和　要拦截所有导弹需要配备的系统数不是一套解决方案．
所以要知道要拦截所有导弹需要配备的系统数（最少）应该重算
先求得每一枚导弹高度的名次比如　389 207 155 300 299 170 158 65
　　　　　　　　　　　　　　　　 1 4 7 2 3 5 6 8
然后按递增但不跳跃的方法取剩下的数据（跳过出现过的名次不算跳跃）
！！
 
to eric.youbin
这样排序一下并没有降低复杂度，没用。
cheka，理解的很对
 
to　jxyghm ：
请你仔细体会这句话
＂在一个序列中解出其最长的降序序列＂
这不就是你问的问题吗？解决呢？解决方法就是用肉眼来看吗？
就好像是＂如果中国队打入了世界杯决赛，中国队就打入世界杯决赛了！＂
我不明白你到底是想没想过怎么解决这个问题！

 
to　jxyghm ：
我想你一定没看明白我的解决方法就是要求一个最长的降序序列！！！
 
eric.youbin
对不起，你说的有道理谢谢
等我想象
 
谁能就此问题写一个简单的第归函数算法（或者其它算法）不胜感激。
 
还有拦截所有导弹的需要的最少系统数
 
我的想法是这样的：
1、首先依次计算出后面比自己高度小的导弹个数，然后根据重新得出的序列，从大到小排
列，遇到相等的数取较大的，最后的个数就是问题1的答案；
2、首先依次计算出后面比自己高度小的导弹个数，相等个数最多的就是问题2的答案。
例如： 389 207 155 300 299 170 158 65
经过第一次运算得出序列：
结果1 7 4 2 4 3 2 1 0
再进行排序,相同的取高度大的，得出：
结果2：389 300 299 170 158 65
那么问题1的答案是打下以下导弹（0：打下，X：不打）：
0 X X 0 0 0 0 0
6个0，最多打下6个，
结果1中相等的个数序列是：
结果3 1 2 2 2 1 2 1 1
2最大，至少需要2套系统。

 
您必须登录或注册才可回复。

Similar threads

S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
D
[原]Delphi XE4 For IOS真机调试配置教程
回复
0
查看
1K
DelphiTeacher的专栏
D
S
[iOS]在苹果手机上使用九宫格输入法时编辑框输入问题的一个临时解决方案
回复
0
查看
698
swish
S
D
[原]OrangeUI－Delphi移动开发利器
回复
0
查看
2K
DelphiTeacher的专栏
D
顶部