问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

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;
声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com
海尔热水器着火一会就熄火出现E2怎么回事 什么网页游戏人气高 求十大网游游戏排行榜 弹弹堂万圣节活动怎么收集糖果 弹弹堂s勋章怎么获得 ...银行说会协同工商局和税务局去我的公司调查,是真的吗? 高中生必须住校吗 双力神洗衣机(双力神洗衣机怎么拆开清洗) 双力神ⅩQB50一397sN洗衣机如何使用? 怎么样加快宫缩开指 如何促进宫缩提前生产 noip1999拦截导弹第二问 NOIP1999提高组第一题导弹拦截问题第二问标答的算法证明 在税务局怎么申领车辆销售发票 关于太原城的问题 龙泊湾说词 项目卖点以及整体沙盘总结 升级完win10打不开图片怎么办? 建发玖珑湾与首创禧悦晴朗哪个比较好点呀? 梦幻西游109力WZ、凌波城、龙宫和花果山哪个门派适合任务号? 济南世贸在华山珑城的哪个方位? WINDOWS10打不开照片 VFP数据库创建索引时什么时候用到转换函数 一立方混凝土多少公斤 混凝土每立方米有多少公斤? 梦见别人借我的车开撞了第三者的车,我却给赔了钱 昨晚梦到结婚然后车被一个朋友借给另一个朋友,然后一直没有开回来,我打开手机定位看到他还在行驶 梦见有人帮自己把车子开出难行路段? 茄子可以祛斑吗 新鲜茄子可以祛斑吗 茄子去斑吗 梦见以前的老板借给我车开是什么意思 NOIP1999 导弹拦截 1999NOIP拦截导弹pascal 1999提高组第1题-拦截导弹 求代码 急急急。。。 NOIP导弹拦截系统第一问 noip2010 NOIP2010普及组复赛(Pascal语言)第三、第四题解题报告及源代码? noip1999提高组 关于noip的问题 导弹拦截问题 C程序 动态规划 防空导弹是怎么拦截导弹的 C++ 拦截导弹问题 常规导弹能拦截吗? 防御导弹问题:最多能拦截多少导弹 鸽子渣的做法 导弹防御系统如何拦截导弹 老鸽子炒肉渣怎么炒 导弹拦截已知轨迹目标时拦截点怎么确定 小饼鸽子渣的做法…请教各位师傅…传说我只在山东见过此菜…做法不知道 导弹被拦截的概率有多大 斑鸠渣的做法 鸽子有没有挆碎的做法