2010年noip复赛第三题导弹拦截答案(Pascal语言)
发布网友
发布时间:2022-05-03 01:45
我来回答
共4个回答
热心网友
时间:2022-06-29 05:25
本题明显是贪心法。我们可以先确定一号系统的半径的平方,在确定二号系统的半径的平方。首先,用一个dis1数组记录下每一个点到一号系统的距离,num1数组记录对应的序号,从小到大快排。然后依次以dis1[1]、dis1[2]......为一号系统半径的平方,由于经过排序,dis1[i]即为一号系统的半径,关键在于找出二号系统的半径,即找出剩下导弹中到二号系统距离最远的那个导弹。若用普通的穷举,则程序复杂度接近O(n²),显然不能接受,于是便想到一种新的思路。我们再用一个dis2数组记录下每一个点到二号系统的距离,num2数组记录对应的序号,从小到大快排。每次找最大距离时,就从大到小扫描,直到找到一个num2[i]没有被一号系统拦截即可暂停,此时的dis2[i]即为最大距离。注意,由于dis2[n],dis2[n-1]......是递减的,所以扫描时可以直接从上一次扫描结束的地方继续向下扫描。
以下是程序:
type arr=array[0..100000] of longint;
var dis1,dis2,num1,num2:arr; //分别记录每个导弹的坐标到一、二号拦截系统的距离的平方和对应的序号
x,y:array[1..100000] of longint; //记录每个导弹的坐标
x1,y1,x2,y2,n,min:longint;
procere init;
var i:longint;
begin
readln(x1,y1,x2,y2);
readln(n);
for i:=1 to n do
begin
readln(x[i],y[i]);
dis1[i]:=sqr(x[i]-x1)+sqr(y[i]-y1); //计算距离的平方
num1[i]:=i;
dis2[i]:=sqr(x[i]-x2)+sqr(y[i]-y2);
num2[i]:=i;
end;
dis1[0]:=0;
dis2[0]:=0;
num1[0]:=0;
num2[0]:=0;
end;
procere qsort(var dis,num:arr; l,r:longint); //快排
var i,j,x,temp:longint;
begin
i:=l;
j:=r;
x:=dis[(l+r) div 2];
while i<j do
begin
while dis[i]<x do inc(i);
while x<dis[j] do dec(j);
if i<=j then
begin
temp:=dis[i];
dis[i]:=dis[j];
dis[j]:=temp;
temp:=num[i];
num[i]:=num[j];
num[j]:=temp;
inc(i);
dec(j);
end;
end;
if l<j then qsort(dis,num,l,j);
if i<r then qsort(dis,num,i,r);
end;
procere work;
var f:array[0..100000] of boolean; //记录每枚导弹是否被一号系统拦截,true表示未被拦截
i,k:longint;
begin
qsort(dis1,num1,1,n); //分别对dis1、dis2排序
qsort(dis2,num2,1,n);
k:=n;
fillchar(f,sizeof(f),true);
min:=maxlongint;
for i:=0 to n do
begin
f[num1[i]]:=false;
while (k>=0) and not f[num2[k]] do dec(k); //寻找未被一号系统拦截的导弹到二号系统的距离的平方的最大值
if dis1[i]+dis2[k]<min then min:=dis1[i]+dis2[k];
end;
end;
begin
assign(input,'missile.in');
assign(output,'missile.out');
reset(input);
rewrite(output);
init;
work;
writeln(min);
close(input);
close(output);
end.追问你能确认时间能过吗?讲出理由我选你外加20分
追答能过,我在tyvj上测过,程序复杂度为O(nlogn+n)
热心网友
时间:2022-06-29 05:26
先使用贪心法,求出最大拦截数
再用动态规划求出,拦截所有导弹的系统数
热心网友
时间:2022-06-29 05:26
var
a,b,c,d:array[0..10000] of longint;
e,f,i,j,l,n:longint;
begin
readln(n);
e:=1;
f:=0;
a[e]:=1;
for i:=1 to n-1 do
b[i]:=i+n+1;
for i:=1 to n do
c[i]:=i;
for i:=1 to n do
for j:=2 to c[i] do
if c[i] mod j=0 then
begin
while c[i] mod j=0 do
begin
inc(d[j]);
c[i]:=c[i] div j;
end;
end;
for i:=1 to n-1 do
for j:=2 to n do
if (b[i] mod j=0)and(d[j]>0) then
begin
while (b[i] mod j=0)and(d[j]>0) do
begin
b[i]:=b[i] div j;
dec(d[j]);
end;
end;
for i:=1 to n-1 do
if b[i]>1 then
begin
f:=0;
for j:=1 to e do
begin
a[j]:=a[j]*b[i]+f;
f:=a[j] div 10;
a[j]:=a[j] mod 10;
end;
while f>0 do
begin
inc(e);
a[e]:=f mod 10;
f:=f div 10;
end;
end;
for i:=e downto 1 do
write(a[i]);
end.
热心网友
时间:2022-06-29 05:27
for i:=1 to n do f[i]:=1;
for i:=n-1 downto 1 do
for j:=i+1 to n do
if (a[i]>a[j]) and(f[j]>=f[i]) then f[i]:=f[j]+1;