引用
Problem
中国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够达到任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在使用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
Input
最多20个整数,分别表示导弹依次飞来的高度(雷达给出高度数据是不大于30000的正整数)
Output
两个整数M和N。表示:这套系统最多能拦截 M 枚导弹,如果要拦截所有导弹最少要配备 N 套这种导弹系统。
Sample Input
300 250 275 252 200 138 245
Sample Output
5 2
思路:
1.算出每个数字后面都几个小于自己的数字(factor)
2.由最大factor的数字开始替归,寻找往下比自己小,但factor又最大的那个值
3.由这些值串起来,就成了最长的降序序列。
def defend(missiles,fightStack)
return nil if !missiles || missiles.size==0
missilesSize = missiles.size
factors = Array.new(missilesSize)
largest_f_index = missilesSize-1
largest_f = 0
missiles.size.downto(1){|i|
index = i-1
m = missiles.at(index).to_i
m_factor = 0
(i...missilesSize).each{|j|
m_back = missiles.at(j).to_i
m_factor += 1 if m_back<m
}
factors[index] = m_factor
(largest_f_index=index;largest_f=m_factor)if m_factor >largest_f
}
return getFightStack(largest_f_index,missiles,factors,fightStack)
end
def getFightStack(beginIndex,data,factors,fightStack)
return fightStack if beginIndex>=data.length
m = data.at(beginIndex)
m_factor = factors.at(beginIndex)
fightStack << m
nextIndex = beginIndex+1
biggestIndex=data.size
biggestF = 0
(nextIndex...data.size).each{|j|
nextM = data.at(j)
nextF = factors.at(j)
(biggestF=nextF;biggestIndex=j) if nextM<m && nextF>=biggestF
}
getFightStack(biggestIndex,data,factors,fightStack)
end
#
$data = Array.[](300,250,275,252,200,138,240)
m_data = $data
count = 0
while true
fightStack = defend(m_data,Array.new)
break if !fightStack
bestSolution = fightStack if count==0
count += 1
m_data = m_data- fightStack
end
p bestSolution
p bestSolution.size
p count
分享到:
相关推荐
问题背景:某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够达到任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹...
易语言导弹拦截游戏
题目 1:如下图所示的数字三角形。...输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
导弹追击模型-matlab求解.doc
一种敏捷导弹控制系统的设计方法_李友年,导弹的论文,可以看一下
导弹打巫师-少儿编程scratch项目源代码文件案例素材.zip
易语言导弹拦截游戏源码,导弹拦截游戏,创建攻击导弹
导弹拦截飞机的源代码,通过算出两者间的距离,时间差,速度,利用拦截算法算出相关数值,从而实现
采用贪心策略,首先把第一枚导弹的高度存入数组中,意味着要使用第一套拦截系统,然后如果第二枚导弹的高度大于第一枚的话(不能拦截),把第二枚的高度加入数组中(第一枚之后),需要增加另一套拦截系统,如果小于...
MATLAB导弹拦截机动目标仿真
stk弹道导弹防御例子 需要stk9以上版本 通过html交互控制stk,实现导弹防御仿真分析和演示。 1.生成弹道导弹目标; 2.天基、地基、海基预警探测、识别; 3.SBX引导GBI拦截 4.SBX部署优化分析。
内含有matlab导弹制导系统仿真代码和教学视频
【运动学】导弹拦截计算方法matlab源码.md
易语言源码易语言导弹拦截游戏提取方式是百度网盘分享地址
易语言源码导弹拦截游戏.rar
防卫导弹int select(int h[],int n) { int i,j,l[100],max; l[n-1]=1; for(i=n-2;i>=0;i--) { max=0; for(j=i+1;j;j++) if(h[i]>=h[j]&&max[j]) max=l[j]; l[i]=max+1; }
导弹制导系统原理
医药生物行业创新药深度研究系列二:抗体偶联药物(ADC),靶向递送毒性小分子的“生物导弹”-1124-光大证券-29页.pdf
导弹制导系统仿真及教学视频导弹制导系统仿真及教学视频导弹制导系统仿真及教学视频导弹制导系统仿真及教学视频导弹制导系统仿真及教学视频导弹制导系统仿真及教学视频导弹制导系统仿真及教学视频导弹制导系统仿真及...
利用运动学实现导弹仿真飞行-附件资源