用贪心算法编过一次,但找不到程序了,下面是查到的。
如果魔法值>=10,肯定用魔法,不用说
如果>=8并且剩余时间>=2,恢复魔法
当前剩余magic>=6 and 剩余time>=3,恢复
magic>=2 and time>=4,恢复
time>=7,恢复
其余情况走路,至于为什么,动笔算算,例如当magic=6时
如果回魔,3秒内走60米,不回,则走51米,不合算,而如果只剩2秒,那么直接走,因为不够回魔的。特别注明一下magic=0或1,要7秒,因为这种情况要经过2次跳跃才能翻盘。
这样可以求出一定时间内最多走的路程。
如果不够,则直接输出,如果够,则二分时间,查找最大的时间能逃离,输出。二分查找用上了。
program p1431;
var
m,s,t,dis,i,l,r,mid,m1:longint;
begin
readln(m,s,t);m1:=m;
dis:=0;
for i:=1 to t do
begin
if (m>=10) or (m>=6) and (t-i>=1) or
(m>=2) and (t-i>=2) or (t-i>=6) then
begin
if m>=10 then begin m:=m-10;dis:=dis+60;end else m:=m+4;
end
else dis:=dis+17;
end;
m:=m1;
if dis<s then begin writeln('No');writeln(dis);end
else
begin
writeln('Yes');
l:=1;r:=t;
while l<r do
begin
mid:=(l+r) div 2;
dis:=0;m1:=m;t:=mid;
for i:=1 to t do
begin
if (m>=10) or (m>=6) and (t-i>=1) or
(m>=2) and (t-i>=2) or (t-i>=6) then
begin
if m>=10 then begin m:=m-10;dis:=dis+60;end else m:=m+4;
end
else dis:=dis+17;
end;
m:=m1;
if dis>=s then r:=mid else l:=mid+1;
end;
writeln(l);
end;
end.
参考资料:http://zhidao.baidu.com/question/334026522.html