博主主页：Yu·仙笙

专栏地址：洛谷千题详解

目录

题目描述

输入格式

输出格式

输入输出样例

 解析：

C++源码：

Java源码：

Python源码：

---

------------------------------------------------------------------------------------------------------------------------------- 

 ------------------------------------------------------------------------------------------------------------------------------- 

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 D_1D1​、汽车油箱的容量 CC（以升为单位）、每升汽油能行驶的距离 D_2D2​、出发点每升汽油价格PP和沿途油站数 NN（NN 可以为零），油站 ii 离出发点的距离 D_iDi​、每升汽油价格 P_iPi​（i=1,2,…,Ni=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。

输入格式

第一行，D1​，C，D2​，P，N。

接下来有 N 行。

第 i+1 行，两个数字，油站 ii 离出发点的距离 Di​ 和每升汽油价格 Pi​。

输出格式

所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。

输入输出样例

输入 #1

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

输出 #1

26.95

 ------------------------------------------------------------------------------------------------------------------------------- 

 解析：

这道题目应该算是妥妥的贪心+模拟吧……

算法原理如下：

1.枚举途中经过的加油站，每经过一个加油站，计算一次花费；

2.在一个加油站所需要加的油，就是能够支持它到达下一个油价比它低的加油站的量；

3.如果在这个加油站即使加满油，都不能到达一个比它油价低的加油站，就把油箱加满，前往能够到达的加油站中油价最低的那个；

4.如果在这个加油站即使加满油，都不能到达任意一个加油站，也不能到达终点城市，说明无解；

**第三点：为什么要加满油？**因为这样可以减少在下一个加油站（价格更贵）所需要加的油量。

 ------------------------------------------------------------------------------------------------------------------------------- 

C++源码：

#include 
using namespace std;
#define maxn 100000
#define db double
#define INF 9999999 
int n;
db D1, D2, C, P, res, ans, maxx;struct node
{db co, dis;bool friend operator <(const node& a, const node& b){ return a.dis < b.dis; }
}pl[maxn];int Solve(int now)
{int flag = INF; db d = pl[now].dis; for(int i = now + 1; i <= n && pl[i].dis - d <= maxx; i ++){if(pl[i].co < pl[now].co){ans += ((pl[i].dis - d - res) / D2) * pl[now].co;res = 0; return i;}if(flag == INF || pl[i].co < pl[flag].co) flag = i;}if(D1 - pl[now].dis <= maxx){ans += ((D1 - pl[now].dis - res) / D2) * pl[now].co;return INF;}if(flag == INF) { printf("No Solution\n"); return -1; }else{ans += C * pl[now].co; res += (maxx - (pl[flag].dis - d));return flag;}
}int main()
{scanf("%lf%lf%lf%lf%d", &D1, &C, &D2, &P, &n);pl[0].dis = 0, pl[0].co = P;for(int i = 1; i <= n; i ++) scanf("%lf%lf", &pl[i].dis, &pl[i].co);sort(pl, pl + n + 1);maxx = C * D2;int k = 0, t;do{t = Solve(k), k = t;if(t == -1) return 0;}while(t != INF);printf("%.2lf", ans);return 0;
}

 ------------------------------------------------------------------------------------------------------------------------------- 

Java源码：

import java.util.*;
public class 旅行家的预算 {public static void main(String[] args){Scanner sc=new Scanner(System.in);double D1=sc.nextDouble();//两个城市之间的距离double C=sc.nextDouble();//汽车油箱的容量double D2=sc.nextDouble();//每升油能行驶的距离double P=sc.nextDouble();//出发点的油价int N=sc.nextInt();//沿途油站数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));}
}

 ------------------------------------------------------------------------------------------------------------------------------- 

Python源码：

d1, c, d2, p, N = [float(x) for x in input().split()]
ls = list()
ls.append([0, p])
for i in range(int(N)):ls.append([float(x) for x in input().split()])ls.append([d1, float("inf")])# 思路：让每一段的路费最便宜，找到start-end两点间最便宜的油站，买它的油走到终点。若剩下的油不能到达该油站，则找start到该油站之间最便宜的。
# start,end是当前位置和要去的终点， leftover是剩下的油,返回这种情况下的最少花销consume
def MinConsume(start, end, leftover):global ls, c, p, d2Consume = 0# 能直接到终点if start == end:return Consumeelif ls[end][0]-ls[start][0] <= leftover*d2:return Consume# 到不了下一站elif ls[start+1][0]-ls[start][0] > c*d2:return -1*float("inf")# 不能直接到终点else:# 寻找剩下路径第一个最便宜的站cheapp = float("inf")cheapindex = -1for i in range(start, end):if cheapp > ls[i][1]:cheapindex = icheapp = ls[i][1]#考虑当前站到最便宜站的耗费# 剩下的油能到最便宜的站if leftover*d2 >= ls[cheapindex][0]-ls[start][0]:leftover -= (ls[cheapindex][0]-ls[start][0])/d2else:# 剩下的油不能到，则找这两者之间的最便宜的站再加油直到到达那个站，到达那个站后油量为0Consume += MinConsume(start, cheapindex, leftover)leftover = 0# 考虑最便宜站到终点的耗费# 在最便宜的站加油能到终点if c >= (ls[end][0]-ls[cheapindex][0])/d2:Consume += ((ls[end][0]-ls[cheapindex][0])/d2-leftover)*cheapp# 在该站加满油不能到终点，则到该站加满再走到下一个站,可能no solutionelse:Consume += (c-leftover)*ls[cheapindex][1]#走到最便宜的下一站剩的油leftover = c-(ls[cheapindex+1][0]-ls[cheapindex][0])/d2# 最便宜的站能到其下一站if leftover >=0:Consume += MinConsume(cheapindex+1, end, leftover)else:Consume = -1*float("inf")return ConsumeConsume = MinConsume(0, len(ls)-1, 0)
if Consume >= 0:Consume = round(Consume, 2)print("{:.2f}".format(Consume))
else:print("No Solution")

 -------------------------------------------------------------------------------------------------------------------------------