讨论 / 旅行家的预算 我为什么最后一个点错了?
g(x) 2009-10-07 00:07:00
点我顶贴 收藏 删除
通过本测试点|有效耗时172ms

测试结果2: 通过本测试点|有效耗时47ms

测试结果3: 通过本测试点|有效耗时47ms

测试结果4: 运行错误|无效浮点操作

提交代码: program rq347;

type

zhan = record

p,d:real;

end;

var a:array[0..120] of zhan ;

temp:zhan;

ans,ad,c,ever,rest,max,min,dis:real;

i,j,k,m,n,now:integer;

can: boolean;

begin

read(ad,c,ever,a[0].p,n);

for i:= 1 to n do

with a[i] do

read(d,p);

for i:= 1 to n-1 do

for j:= i+1 to n do

if a[i].d>a[j].d then

begin

temp:=a[i];

a[i]:=a[j];

a[j]:=temp;

end;

inc(n);

a[n].d:=ad;

a[n].p:=0;

a[0].d:=0;

max:=c*ever;

now:=0;

rest:=0;

can:=false;

for i:= 1 to n do

if a[i].d-a[i-1].d>max then

begin

writeln(’No Solution’);

halt;

end;

repeat

i:=now;

min:=1000000000;

while a[i].d-a[now].d<=max do

begin

inc(i);

if min>a[i].p then

begin

min:=a[i].p;

j:=i;

end;

if a[i].p<a[now].p then break;

end;

if a[i].d-a[now].d>max then

begin

dis:=a[j].d-a[now].d;

ans:=ans+(c-rest)*a[now].p;

rest:=c-dis/ever;

now:=j;

continue;

end;

dis:=a[j].d-a[now].d;

ans:=ans+((dis/ever)-rest)*a[now].p;

rest:=0;

now:=j;

if now=n then

begin

can:= true;

writeln(ans:0:2);

halt;

end;

until can;

end.

查看更多回复
提交回复