UC知道pascal编程:拦截导弹
来源：百度知道 编辑：UC知道 时间：2024/05/15 17:17:07
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入格式
输入数据为两行，
第一行为导弹的数目N
第二行导弹依次飞来的高度，所有高度值均为不大于30000的正整数。
输出格式
输出只有一行是这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。两个数据之间用一个空格隔开.
样例输入
8
389 207 155 300 299 170 158 65
样例输出
6 2
输入格式
输入数据为两行，
第一行为导弹的数目N
第二行导弹依次飞来的高度，所有高度值均为不大于30000的正整数。
输出格式
输出只有一行是这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。两个数据之间用一个空格隔开.
样例输入
8
389 207 155 300 299 170 158 65
样例输出
6 2
min[]表示的是已有系统的拦截导弹最低高度，进来新的新的导弹后导弹在已有系统中筛选如果MIN[J]<A[I]则更新系统J的最低高度，另外已知MIN[]为递增，所以
如果J可以，则J+1--K都可以。我们用贪心策略用J系统即可。
var
i,j,k,n:integer;
a,b:array[1..1000] of longint;
f:text;
function max:longint;
var
i,j,k:integer;
m:longint;
begin
m:=1;
for i:=n-1 downto 1 do
begin
k:=1;
for j:=i+1 to n do
if (b[j]+1>k)and(a[i]>a[j]) then
begin
k:=b[j]+1;
if m<k then m:=k;
end;
b[i]:=k;
end;
max:=m;
end;
function sys:integer;
var
i,j,k,m:integer;
min:array[1..100] of integer;
begin
min[1]:=a[1];k:=1;m:=a[1];
for i:=2 to n do
begin
j:=1;
if a[i]<min[1] then min[1]:=a[i]
else
begin
while (a[i]>min[j])and(j<=k) do j:=j+1;