问题描述：
题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离i、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入
输入第一行有5个数：D1，c，D2，P，N(前四个为实数，N为整数,N<=1000)
后面有N行，每行两个实数，分别表示对应的加油站离出发点的距离，与每升汽油的价格
输出
输出仅一行，即最少花费
这道题我找到了一个反例，至今我想的所有贪心算法都不能解决！
点 油价 距离
0 5 0 （起点）
1 10 10
2 30 15
3 -- 30 （终点）
(每升油可走一公里）
一般的贪心算法从起点加满，先走到2
但事实上从起点加10升，先走到1，在加满走到3才是最佳选择
什么算法才可以克服此反例？望赐教
问题解答：
看到题目后，很容易想到递推，但是又不知道具体怎样做。我们可以先分析一下题目，用手工算
几个数据，看能不能受到启发（注意：这是一个很重要的思路!!）
例如可以先分析样例数据（这是理解题意思必须的，因为样例不会错）
算了一下吗？好了，我问你，如果你是司机，你会怎么办呢？
尽量买便宜的，贵的就买“刚刚可以到下一站”？对不对呢？
举出反例很容易，但是我们不能轻易放弃这个思路，可以接着想下去。
不能保证全局最优，我们就试着改进我们的方法。
事实上，要用的油是确定的（D1/D2），价钱最便宜的油的站Q的油显然应该多买，至少：
到达Q这个油站时汽车剩油不为0的方案一定不是最优的。
这是因为，如果剩下P升油，显然不如当初少买P升，改在Q这里买P升划算！（Q最便宜嘛！）
哈哈，有一点思路了吧！就是把较优解改进为最优解啦！
算法如下：
每次都假装装满油，用的时候先用便宜的，因为把贵的留在后面“反悔”(被替换成更便宜的油)不是更爽吗？！
这样计算费用时只考虑真正使用的，假装装满时就不要再算一次了。你看看程序中是不是只有两处修改了cost？
我很懒，因此就默认油站是按离起点由近及远给出的。
输入后面是先把油费由贵到便宜排序,第i贵的站是place[i]，以便选择。
下面的程序中主要部分是那个循环，它做了以下事情：
1)假装装满油：gas[i]:=c-nowp; nowp是现在有的油，gas[i]是车上第i站的油的体积。
2)替换：现有的油如果有比当前站（第i站）贵的，改为i号油：gas[i]:=gas[i]+gas[j]; gas[j]:=0;
3)行驶：依次选择最便宜的油行驶路程distance,就是个循环for j:=n downto 0
经过这样分析,程序是不难写出了，程序长一点，是为了写得更易懂。
基础较好的同学也可以用优先队列（例如用堆来实现）来进行替换和使用油，这里只用了最简单的方法模拟，
效率并不高。
program FenQuPrepare_Day4_Task3_FQ99P3;
type
real=extended;
const
fn_in='input.txt';
maxn=100;
var
ans,c,d1,d2:real;
can:boolean;
n:Integer;
d:array[0..maxn] of real;
p:array[0..maxn] of real;
procedure init;
var s:string;
i:Integer;
begin
assign(input,fn_in);
reset(input);
readln(d1,c,d2,p[0],n);
for i:=1 to n do readln(d[i],p[i]);
end;
procedure main;
var cur,i,j:Integer;
rest,min:real;
begin
can:=true;
for i:=1 to n do
if (d[i]-d[i-1])>c*d2 then can:=false;
if d1-d[n]>c*d2 then can:=false;
if not can then exit;
rest:=0;
ans:=0;
for cur:=0 to n do
begin
min:=1e10;
i:=cur;
while (i<=n) and ((d[i]-d[cur])<=c*d2) do
begin
if p[i]<min then
begin
min:=p[i];
j:=i;
end;
inc(i);
end;
if j=cur then
begin
if c*d2>(d1-d[cur]) then
begin
if rest*d2<d1-d[cur] then
begin
ans:=ans+p[cur]*((d1-d[cur])/d2-rest);
rest:=(d1-d[cur])/d2;
end;
end else
begin
ans:=ans+p[cur]*(c-rest);
rest:=c;
end
end else
begin
if rest*d2<d[j]-d[cur] then
begin
ans:=ans+p[cur]*((d[j]-d[cur])/d2-rest);
rest:=(d[j]-d[cur])/d2;
end;
end;
rest:=rest-(d[cur+1]-d[cur])/d2;
end;
end;
procedure out;
begin
if can then
begin
ans:=round(ans*100)/100;
writeln(ans:0:2);
end else writeln('No solution');
end;
begin
init;
main;
out;
end.
上海旅游网