P1201旅行家的预算
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
4.8旅行家的预算 算法解析：（问题处理方法多样，在此仅谈分治法的处理） 【问题分析】 看到这道题，许多人都马上判断出穷举是不可行的，因为数据都是以实数的形式给出的。但是，不用穷举，有什么更好的方法呢？比较容易想到的是分治法。 一、接下来考虑具体如何分的过程： （1）首先找出所有加油站中(从后向前)油价最低那个，显然汽车至该油站时油箱应为空。 （2）这样就可将起点至该站与该站至终点作为两段独立考虑，分别求其最小费用，二者之和即为总费用。 二、分治过程中的边界处理： （1）这样一直分下去，若某段只有起点与终点两个加油站时无需再分， （2）如某一段油价最低的加油站即为起点，（特别处理！） 1、则如能一次加油即到达该段终点则最好，直接计算结果，结束。 2、若不能，则加满油再考虑油箱有油情况下的二分法，找出油价次低的加油站点： A、不能到达。考虑起点之外所有的加油站中从后往前油价最低的加油站， 若该加油站位于起点加满油后不能到达之处，则到达该站时油箱应该为空，以该站为界将全程分为两个独立段考虑，前半段为有油情况，后半段为无油情况。 B、能到达。第二种情况，若该加油站处于起点加满油后能到达之处，则将该段总路程缩短为该加油站至终点的情况，该加油站在该段路程中最便宜，若从该站加满油仍不能到达终点，则继续分治即可。 （本题，在分方面还是比较直观的，但是对于边界，以及各种情形的考虑，略现烦琐一些！） 变量说明：程序被设计成一个递归函数money，形式参数start表示起点站，形式参数stop表示终点站，形式参数rest表示到达加油站start时汽车油箱余下的油的容量，money函数最终计算出从加油站start到stop区间内的最小费用。 program trip; const maxn=100; var {d[i]：表示第i个站点距离出发点的距离，p[i]：表示第i个加油站的加油时的油价， 其中d[0]：表示出发点；d[i+1]：表示终点} d,p:array[0..maxn+1]of real; s,c,per,len:real; i,n:integer; function minp(s,t:integer):integer;{找出加油站[s,t]闭区间内，加油站的最小费用的加油站点} var i,k:integer; begin k:=s; for i:=s+1 to t do if p[i] minp:=k; end;
function money(start,stop:integer;rest:real):real; var
k:integer; begin
{stop-start=1，则表示中间已无加油站可提供选择了，直接处理输出结果！函数结束！} if stop-start=1 then begin money:=((d[stop]-d[start])/per-rest)*p[start]; exit; end;
k:=minp(start,stop-1);{找出闭区间[start,stop-1]间费用最低的加油站点标号}
{k<>start，费用最低的加油站k，不在起点start处，则汽车开到k处时，应用完所有汽油，分成两段进行考虑：}
if k<>start then money:=money(start,k,rest)+money(k,stop,0) else begin{{k＝start，费用最低的加油站在起点start处！分两种情形考虑：} {1：能直接到达终点，直接计算输出结果！}
if d[stop]-d[start]<=len then money:=((d[stop]-d[start])/per-rest)*p[start]
{2：不能直接到达终点，需加满油箱！}
else begin
{找出次低价的加油站标号：k，对是否能到达k处分两种情形考虑：}
k:=minp(start+1,stop-1);
{1、从start处加满油箱容量c，能到达次加油站k处的处理}
if d[k]-d[start]<=len then money:=(c-rest)*p[start]+money(k,stop,c-(d[k]-d[start])/per)
else begin
{2、从start处加满油箱，仍不能到达次加油站k处的处理}
money:=money(start,k,rest)+money(k,stop,0);
end; end; end; end; begin
assign(input,'data4.out'); reset(input); readln(s,c,per,p[0],n);
for i:=1 to n do readln(d[i],p[i]); d[n+1]:=s;
len:=c*per;{汽车加满油箱后，能跑的最远的距离}
{考虑一下：何种情形下，汽车无论如何也不可能到达终点， 也就是到达下个加油站之前半路就没油了} for i:=n downto 0 do begin if d[i+1]-d[i]>len then begin writeln('No solution!'); halt; end; end;
writeln(money(0,n+1,0):0:2); close(input); end.
本文来源：https://www.wddqw.com/doc/252749acdd3383c4bb4cd24d.html