首页 > 代码库 > 导弹拦截--优化算法

导弹拦截--优化算法

2024-08-16 23:17:42   211人阅读

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，并且输出如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

第一问，很简单，最长不上升子序列+优先队列，O（NlogN）

第二问，可以转化成最长上升子序列（自己想），时间复杂度同上。

 1 var
 2   s,s2:string;
 3   i,j,t,n,tail:longint;
 4   a,queue:array[0..10000]of longint;
 5 function posdown(value:longint):longint;
 6 var
 7   middle,left,right:longint;
 8 begin
 9   left:=1;
10   right:=tail+1;
11   while left<right do
12   begin
13     middle:=(left+right) div 2;
14     if queue[middle]>=value then left:=middle+1
15     else right:=middle;
16   end;
17   posdown:=left;
18 end;
19 function posup(value:longint):longint;
20 var
21   middle,left,right:longint;
22 begin
23   left:=1;
24   right:=tail+1;
25   queue[right]:=maxlongint;
26   while left<right do
27   begin
28     middle:=(left+right) div 2;
29     if queue[middle]<value then left:=middle+1
30     else right:=middle;
31   end;
32   posup:=left;
33 end;
34 begin
35   readln(s);
36   s:=s+‘ ‘;
37   j:=1;
38   for i:=1 to length(s) do
39   begin
40     if s[i]=‘ ‘ then
41     begin
42       inc(n);
43       s2:=copy(s,j,i-j);
44       val(s2,a[n],t);
45       j:=i+1;
46     end;
47   end;
48   tail:=0;
49   for i:=1 to n do
50   begin
51     t:=posdown(a[i]);
52     queue[t]:=a[i];
53     if t>tail then inc(tail);
54   end;
55   writeln(tail);
56   tail:=0;
57   fillchar(queue,sizeof(t),0);
58   for i:=1 to n do
59   begin
60     t:=posup(a[i]);
61     queue[t]:=a[i];
62     if t>tail then inc(tail);
63   end;
64   writeln(tail);
65 end.

 

导弹拦截--优化算法


联系
我们