（详解）旅⾏家的预算（JAVA实现）蓝桥杯算法训练ALGO-15旅⾏家的预算
问题描述
  ⼀个旅⾏家想驾驶汽车以最少的费⽤从⼀个城市到另⼀个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能⾏驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五⼊⾄⼩数点后两位。如果⽆法到达⽬的地，则输出“No Solution”。
输⼊格式
  第⼀⾏为4个实数D1、C、D2、P与⼀个⾮负整数N；
  接下来N⾏，每⾏两个实数Di、Pi。
输出格式
  如果可以到达⽬的地，输出⼀个实数（四舍五⼊⾄⼩数点后两位），表⽰最⼩费⽤；否则输出“No Solution”（不含引号）。
样例输⼊
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
样例输出
26.95
这题的变量⽐较多，所以在此之前我们得捋⼀捋变量之间的关系。根据题⽬所给的变量我们还可以得出汽车满油状态下能⾏驶的⾥程。
我把已知变量列出如下。
double Double();//两个城市之间的距离
double Double();//汽车油箱的容量
double Double();//每升油能⾏驶的距离
double Double();//出发点的油价
int Int();//沿途油站数
double[] Pi=new double[N+2];//每个站点的油价
double[] D=new double[N+2];//离出发点的距离
double MaxDistance=D2*C;
double fee=0;//总费⽤
double remain=0;//汽车剩余的油量
算法分析
我们需要求的结果是最少的费⽤。因此我们每个加油站的费⽤是我们要考虑的重要因素之⼀。
⾸先我们排除⽆解的情况，只要存在两个节点的距离⼤于汽车能⾏驶的最⼤距离则⽆解。(PS：循环是从0到N，因为在初始化数据D与Pi时我将起点与终点也加⼊了进去，完整代码贴在最后。)
for(int i=0;i<=N;i++)
if(D[i+1]-D[i]>MaxDistance){
System.out.println("No Solution");
return;
}
我们总是希望在加油的时候，能在汽车可⾏驶的最⼤距离MaxDistance之中，到油价更低的加油站进⾏加油。
基于此我们考虑可能的两种情况。每次到达加油的站点 i时做⼀次判断。
1.从当前站点的下⼀个站点i+1到汽车能⾏驶的最⼤距离MaxDistance之间存在油价更低的位置j
那么我们就从当前站点i加油，刚好能到达j。
2.当前站点的下⼀个站点j到j+MaxDistance之间不存在油价更低的位置
这种情况下我们就把油加满！因为这个地⽅是⽬前⽽⾔油价最低的点，那我们就需要贪⼼⼀点，有多少加多少。直到能跑到最远的位置。那么现在问题来了，我们要如何定位——从当前位置i出发，到下⼀站j?
遍历i站点的下⼀个站点i+1到终点N+1的每⼀个站点，分两步⾛：
1.如果从当前位置到下⼀个站点者之间的距离⼤于MaxDistance，退出循环，说明汽车能到达的位置是j-1，即必须要到j-1这⼀站加油了！
2.如果出现了⽐i站点油价便宜的地⼉，因为旅⾏家是贪⼼的，所以我们得锁定这个j，⽴马跑到这个站点去加油。
int j=i;
for(j=i+1;j<=N+1;j++)
{
if(D[j]-D[i]>MaxDistance){
j-=1;//最⼤⾏驶距离⽆法到达j，因此最⼤到达j-1站点
break;
}
if(Pi[j]<=Pi[i])
break;//到了下⼀个更便宜的加油站
}
到了现在我们到了每加⼀次油后，接着要前往的下⼀站。按照⼀开始讨论的两种情况，对if(Pi[j]<=Pi[i])//到了下⼀个更便宜的加油站
{
fee+=((D[j]-D[i])/D2-remain)*Pi[i];//更新费⽤
remain=0;//更新到达下⼀个加油站后的剩余油量
}
else//没有到加满油
{
fee+=(C-remain)*Pi[i];
汽车油箱容量
remain=C-(D[j]-D[i])/D2;
}
整个过程就是这样，完整代码如下
import java.util.*;
public class旅⾏家的预算{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
double Double();//两个城市之间的距离double Double();//汽车油箱的容量double Double();//每升油能⾏驶的距离double Double();//出发点的油价
int Int();//沿途油站数
double[] Pi=new double[N+2];//每个站点的油价double[] D=new double[N+2];//离出发点的距离double MaxDistance=D2*C;
//初始化距离和油价数组，将起点与终点也加⼊其中  D[0]=0;Pi[0]=P;
D[N+1]=D1;Pi[N+1]=0;
for(int i=1;i<=N;i++){
D[i]=sc.nextDouble();
Pi[i]=sc.nextDouble();
}
double fee=0;
double remain=0;
//⽆解的情况
for(int i=0;i<=N;i++)
if(D[i+1]-D[i]>MaxDistance){
System.out.println("No Solution");
return;
}
//有解，开始遍历每⼀个站点
int i=0;
while(i<=N)
{
int j;
for(j=i+1;j<=N+1;j++)
{
if(D[j]-D[i]>MaxDistance)
{
j-=1;//最⼤⾏驶距离⽆法到达j，因此最⼤到达j-1站点break;
}
if(Pi[j]<=Pi[i])
break;//到下⼀个更便宜的加油站
}
if(Pi[j]<=Pi[i])//到了下⼀个更便宜的加油站
{
fee+=((D[j]-D[i])/D2-remain)*Pi[i];//更新费⽤
remain=0;//更新到达下⼀个加油站后的剩余油量}
else//没有到加满油
{
fee+=(C-remain)*Pi[i];
remain=C-(D[j]-D[i])/D2;
}
i=j;//前往下⼀个加油站，滴滴滴！
}
System.out.println(String.format("%.2f", fee));
}
}
有⼀点要注意的是倒数第⼆⾏，每次循环完毕后，要把下⼀站的值赋给i，表⽰我们即将前往的下⼀站。