洛谷千题详解 | P1016 [NOIP1999 提高组] 旅行家的预算【C++、Java、Python语言】

博主主页：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, d2
    Consume = 0
    # 能直接到终点
    if start == end:
        return Consume
    elif 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 = -1
        for i in range(start, end):
            if cheapp > ls[i][1]:
                cheapindex = i
                cheapp = ls[i][1]
        
        #考虑当前站到最便宜站的耗费
        # 剩下的油能到最便宜的站
        if leftover*d2 >= ls[cheapindex][0]-ls[start][0]:
            leftover -= (ls[cheapindex][0]-ls[start][0])/d2
        else:
        # 剩下的油不能到，则找这两者之间的最便宜的站再加油直到到达那个站，到达那个站后油量为0
            Consume += 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 solution
        else:
            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 Consume
 
Consume = MinConsume(0, len(ls)-1, 0)
if Consume >= 0:
    Consume = round(Consume, 2)
    print("{:.2f}".format(Consume))
else:
    print("No Solution")
 

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