2328: [HNOI2011]赛车游戏 - BZOJ

2328: [HNOI2011]赛车游戏 - BZOJ

先把一定要减的费用先减掉,就是b*s*len(上坡路),下坡路就设一个初速度,使耗油为0,如果没油了,就无法到达

然后考虑加速

对于长度为len的路,增加v的速度需要len*a*v的油,与len成正比

然后又因为原来的速度越小,增加等量v的增益越高,所以每次都从最小的速度开始加(不超过第二小),还有不要超过vmax

 const
maxn=;
var
t,n:longint;
a,b,vmax,f:double;
len,s,v:array[..maxn]of double; procedure init;
var
i:longint;
x,y:double;
begin
read(a,b,vmax,f,n);
for i:= to n do
begin
read(x,y);
len[i]:=sqrt(sqr(x)+sqr(y))/;
s[i]:=y/x;
if s[i]> then f:=f-len[i]*b*s[i];
if s[i]< then v[i]:=-b*s[i]/a
else v[i]:=;
end;
end; procedure swap(var x,y:double);
var
t:double;
begin
t:=x;x:=y;y:=t;
end; procedure sort(l,r:longint);
var
i,j:longint;
y:double;
begin
i:=l;
j:=r;
y:=v[(l+r)>>];
repeat
while v[i]<y do
inc(i);
while v[j]>y do
dec(j);
if i<=j then
begin
swap(s[i],s[j]);
swap(v[i],v[j]);
swap(len[i],len[j]);
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end; procedure work;
var
i,j:longint;
sum:double;
begin
sort(,n);
for i:= to n do
if v[i]>vmax then v[i]:=vmax;
v[n+]:=vmax;
sum:=;
for i:= to n do
begin
sum:=sum+len[i];
if v[i]<>v[i+] then
begin
if f>=(v[i+]-v[i])*sum*a then
begin
f:=f-(v[i+]-v[i])*sum*a;
v[i]:=v[i+];
end
else
begin
v[i]:=v[i]+f/(sum*a);
break;
end;
end;
end;
for j:=i- downto do
v[j]:=v[j+];
if v[]= then
begin
writeln('IMPOSSIBLE');
exit;
end;
sum:=;
for i:= to n do
sum:=sum+len[i]/v[i];
writeln(sum::);
end; begin
read(t);
while t> do
begin
init;
if f< then writeln('IMPOSSIBLE')
else work;
dec(t);
end;
end.
上一篇:URL传递中文:Server.UrlEncode与Server.UrlDecode


下一篇:我的Android进阶之旅------>报 error: Apostrophe not preceded by \ 的错误解决办法