某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
例如导弹飞来的高度依次为293 287 295 286 292,第1套拦截系统拦截的导弹高度分别为293 287 286,第2套拦截的导弹高度分别为295 292,因此至少需要2套拦截系统才能拦截所有导弹。
[C/C++]代码
#include<bits/stdc++.h> #define MAX 1005 using namespace std; int h[MAX],k,n,xt[MAX],p; int main() { n=0; while(cin>>h[n]) _______(1)_______; k=1; xt[0]=h[0]; for(int i=1;i<n;i++) { ______(2)__________; for(int j=0;j<k;j++) { if(h[i]<=xt[j]) { _______(3)__________; p=1; break; } } if(!p) { xt[_______(4)________]=h[i]; } } cout<<k<<endl; }
[Python]代码:
h=[_____(1)______ for t in input().split()] n=1 xt=[h[0]] for i in h: _____(2)__________ for j in range(len(xt)): if i<=xt[j]: ______(3)_______ flag=True break if not flag: xt.append(i) _____(4)________ print(n)