83 条题解
-
0
hhdllhflower LV 10 @ 2009-05-30 19:00:49
贪心and指针
program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil^.way>maxway then
begin
init:=false;
exit
end;
init:=true;
end;
procedure buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procedure solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s -
0
var
c,d1,u,minp,maxp,m,e:real;
d,p:array[0..101] of real;
n,i,a,t,minpn:integer;
b:boolean;
begin
readln(u,c,d1,p[0],n);
d[0]:=0;d[n+1]:=u/d1;b:=true;t:=0;maxp:=0;m:=0;e=0;
for i:=1 to n do begin
readln(d[i],p[i]);
d[i]:=d[i]/d1;
end;
for i:=1 to n+1 do
if d[i]-d>c then b:=false;
for i:=0 to n do
if p[i]>maxp then maxp:=p[i];
if b then begin
while t -
0
无敌贪心！！！
---|---|---|---|---|---|---|---|---|---|---|--
var cost,go,d1,c,d2,q,nowoil:real;
i,j,n:longint;
p,d:array[0..1001]of real;
over:boolean;
function lowest(j:longint):longint;
var i,g:longint;min:real;
begin
min:=10000000;for i:=j+1 to n do
begin
if d[i]-d[j]go then
begin
writeln('-1');
end
else
begin
writeln(d1*p[0]/d2:0:2);
end;
end
else
if d1-d[n]>go then writeln('-1')
else
begin
over:=false;
i:=0;
cost:=0;
nowoil:=0;
while not(over) do
begin
j:=lowest(i);if i=n then
begin
over:=true;
cost:=((d1-d[n])/d2-nowoil)*p[i]+cost;
nowoil:=0;
end
else
if p[j]>p[i] then
begin
if go+d[i]>d1 then
begin
over:=true;
cost:=cost+(d1-d[i])/d2*p[i];
nowoil:=0;
end
else
begin
cost:=cost+(c-nowoil)*p[i];
nowoil:=c-(d[j]-d[i])/d2;
end;
end
else
begin
if nowoil -
0
破晓Daybreak LV 8 @ 2009-01-06 23:01:23
Accepted 有效得分：100 有效耗时：0ms
一次AC：） 56行。
策略是 走到能走到之内的第一个价格比当前所在点便宜的加油站，如果之后能走到的所有站都比当前点贵 那么就加满油 走到能走到的最便宜的一个站。所以还需要一个变量cnow用来记录当前邮箱油量多少。然后就是注意细节处理，起点和终点的加油价格（终点为0）距离（终点+1为d1/d2，终点+2为max）以及将所有的距离km处理为需求油量L的化简处理。还有最后四舍五入(round(cost*100)/100):0:2的处理。
然后就一次A啦~贪心策略的代码……变量什么的应该是通俗易懂吧 囧
procedure found;
begin
nowt:=now+1;
min:=maxp;
while lp[nowt]-lp[now] -
0
-
0
jtjxhjl321 LV 3 @ 2008-10-27 12:47:54
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msprogram p1253;
var
a:array [1..105,1..2] of real;
s,c,d1,d2,t:real;
d,p:array [0..101] of real;
n,i,j,top,k:longint;
begin
readln(d1,c,d2,p[0],n);
d[0]:=0;
p[n+1]:=1000000;
d[n+1]:=d1;
for i:=1 to n do begin
readln(d[i],p[i]);
if d[i]-d>c*d2 then begin
write(-1);
halt;
end;
end;
if d1-d[n]>c*d2 then begin
write(-1);
halt;
end;
top:=1;
a[top,1]:=p[0];
a[top,2]:=c;
s:=p[0]*c;
for i:=1 to n+1 do
begin
t:=(d[i]-d)/d2; {use}
while a[1,2]t then a[1,2]:=a[1,2]-t;{use}
j:=1; {find}
while (a[j,1] -
0
honggaixin LV 6 @ 2008-10-15 22:53:45
貪心祘法
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil^.way>maxway then
begin
init:=false;
exit
end;
init:=true;
end;
procedure buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procedure solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s -
0
Magic_Ming LV 3 @ 2008-10-03 14:22:48
崩溃类。。。
本来不是NO SOLUTION的咩
怎么变-1了 害我重新提交了一次。。。55555 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
在书上见了这题!二分和贪心以前少做!就打算做!按照书上提示用二分!因此进入了痛苦的一个晚上!最后还是没能AC!而且程序超长!还有莫名其妙的错误!
最后从头用一路贪心!终于接近了满分(80);因为一个细节没注意!而且是很重要的细节!但是这居然得80分~经过修改终于AC拉! -
0
Endless.K. LV 3 @ 2008-09-03 23:29:17
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms我承认我比较无聊，拿的BC。。
hhdllhflower
LV 10
@ 2009-05-30 19:00:49
