NOIP2010普及组复赛（Pascal语言）第三、第四题解题报告及源代码？

第三题 两个导弹，求拦截导弹的最小和半径（半径的平方和）
难度：★★★★☆
时间：具体是一小时还是两小时记不清了
考试时的思路：贪心，求到两个圆心的最大值，然后如果该点到A的距离小于到B 的距离，则半径为该点到A的距离，另一个半径用同样的方法求
结果：20分
错误点：这样求出的半径会使有些点拦截不到
正确思路：排序+穷举
求所有点到两个圆心的距离，按到A圆的距离排序，按升序，则前i个给A，后面的给B
例如：到A的距离：1 2 3 4 5
到B 的距离：2 5 4 3 1
如果i=3，前3个让A拦截，r=3，后两个让B拦截，r：=3
如果i=4，前4个让A拦截，r=4，后一个让B拦截，r：=1
按照这个思路，需要排序之后穷举i:=1 to n do，然后将i+1 to n 中取最大值，归B拦截，这样的话时间复杂度为：O(N)2，超时； 反过来思考：从后向前进行递推，
N到n的最大值为n 设为F[n]
N到n-1 的最大值为
n和n-1 之间的最大值 为 max（f[n],b[n-1]）
N到n-2 的最大值为 max（f[n-1],b[n-2]）
这样时间复杂度接近 O(n)，就可以过了
结果：满分
代码：
program ex01;
const
inf='missile.in';
ouf='missile.out';
varx1,x2,y1,y2,i,j,k,tot,n,l,r,max1:longint;
x,y:array[1..100000] of longint;
a,b,f,d:array[1..100000] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
procedure quicksort(l,r:longint);//到（x1,y1）点的距离排序
var
i,j,m,p:longint;
begin
i:=l;j:=r;
m:=a[(i+j) div 2];
repeat
while a[i]while a[j]>m do dec(j);
if i<=j then
begin
p:=a[i];a[i]:=a[j];a[j]:=p;
p:=b[i];b[i]:=b[j];b[j]:=p;
inc(i);dec(j);
end;
until i>j;
if l if i end;
begin
assign(input,inf);
reset(input);
assign(output,ouf);
rewrite(output);
readln(x1,y1,x2,y2);
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
for i:=1 to n do
begin
a[i]:=sqr(x[i]-x1)+sqr(y[i]-y1);
b[i]:=sqr(x[i]-x2)+sqr(y[i]-y2);//求出到两个圆心的距离
end;
l:=1;r:=n
quicksort(l,r);//快排，不解释
for i:=n downto 1 do
begin
d[i]:=f[i+1]+a[i];//A和B的半径和
f[i]:=max(b[i],f[i+1]);//找后i个距B的最大值
end;
max1:=maxlongint;
for i:=1 to n do
if d[i] writeln(max1);
close(input);close(output); end.

第四题 人机大战，在获胜的前提下求出最大的默契值
难度：★★★☆☆
时间：10分钟左右，最后十分钟，一个骗分的程序
思路：当时按照样例，想的是找所有数中的最大数，然后人取一个，电脑取一个，类似于模拟，，不过是错误的
最后没时间了，writeln（‘0’）
分数：0分
正确思路：贪心
1）找所有数中次大的，因为你选定默契值最大的武将之一后，最大值就被电脑“咔嚓”掉了。于是我们只可能取到次大值，而次大值中最大的就一定最优了。
2）这个值一定能取到，因为最大值被人机破坏，而人又取到的次大值，所以我们一定会赢（电脑是人设计滴~~！！）
代码：
program ex01;
const
inf='sanguo.in';
ouf='sanguo.out';
var
a:array[1..500,1..500] of longint;
n,i,j,k,tot,temp,max:longint;
begin
assign(input,inf);reset(input);
assign(output,ouf);rewrite(output);
fillchar(a,sizeof(a),0);
readln(n);
for i:=1 to n do
for j:=i+1 to n do
begin
read(a[i,j]);
a[j,i]:=a[i,j];//做成表格
end;
max:=-maxlongint;
k:=-maxlongint;
temp:=-maxlongint;//最终所求的数
for i:=1 to n do begin
max:=-maxlongint;//最大值
k:=-maxlongint;//次大值
for j:=1 to n do
if a[i,j]>max then
begin
k:=max;//记录次大值
max:=a[i,j];
end
else if a[i,j]>k then k:=a[i,j]
if k>temp then temp:=k;//与前一行的次大值进行比较
end;
writeln('1');
writeln(temp);
close(input);
close(output);
end.
最终评价 本套题交了3遍
第一次：22个测试点（10 ，10，2，0 ）(思路错误)
第二次：30个测试点（10，10，10）
第三次：全过

type
pos=record
d1,d2:qword;
end;
var
a:array[1..100000]of pos;
x1,x2,y1,y2,x,y:integer;
n,i:longint;
ans,max:qword;
function f(k:longint):longint;
var
i:longint;
begin
f:=k;
for i:=k+1 to n do
if a[i].d2>=a[f].d2 then f:=i;
end;
procedure qsort(l,r:longint);
var
i,j,m:longint;
t:pos;
begin
i:=l;j:=r;
m:=a[(i+j) div 2].d1;
repeat
while a[i].d1 while a[j].d1>m do dec(j);
if i<=j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);dec(j);
end;
until i>j;
if i if lend;
begin
assign(input,'missile.in');reset(input);
assign(output,'missile.out');rewrite(output);
readln(x1,y1,x2,y2);
readln(n);
for i:=1 to n do
begin
readln(x,y);
a[i].d1:=sqr(x-x1)+sqr(y-y1);
a[i].d2:=sqr(x-x2)+sqr(y-y2);
end;
qsort(1,n);
max:=f(1);//求出离b最远的序号
ans:=a[max].d2;//离b最远的距离
for i:=1 to n do
begin
if max=i then max:=f(i+1);
if ans>a[max].d2+a[i].d1 then ans:=a[max].d2+a[i].d1;
end;
writeln(ans);
close(input);close(output);
end.
var
a:array[1..500,1..500]of longint;
n,i,j:integer;
max,max2,ans:longint;
procedure init;
begin
fillchar(a,sizeof(a),0);
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
if i read(a[i,j]) else
if i>j then
a[i,j]:=a[j,i];
end;
ans:=0;
end;
procedure main;
begin
for i:=1 to n do
begin
if a[i,1]>a[i,2] then
begin
max:=a[i,1];
max2:=a[i,2];
end else
begin
max:=a[i,2];
max2:=a[i,1];
end;
for j:=3 to n do
begin
if max begin
max2:=max;
max:=a[i,j];
end else if max2 max2:=a[i,j];
end;
if max2>ans then ans:=max2;
end;
writeln(1);
writeln(ans);
end;
begin
assign(input,'sanguo.in');reset(input);
assign(output,'sanguo.out');rewrite(output);
init;
main;
close(input);close(output);
end.