P1016 旅行家的预算-白红宇

P1016 旅行家的预算

阅读量：5016 次

发布时间：2019-06-12

本文共 2554 字，大约阅读时间需要 8 分钟。

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离

输入输出格式

输入格式：

第一行，

接下来有

第

输出格式：

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

输入输出样例

输入样例#1：

275.6 11.9 27.4 2.8 2102.0 2.9220.0 2.2

输出样例#1：

26.95

说明

$哇哦，这道题我做的可，，真认真。。。$

$我就感觉这是个模拟嘛，，，$

$写出来之后发现我那些取优的操作，可不就是贪心。。qwq。$

$首先我们按照题目要求输入第一行，$

$一定要注意题目中说的：n可以为0（25分）$

$所以我们先来处理n==0的情况；$

$n为0，也就是说从起点到终点，中间没有任何站点可供加油，$

$所以我们不得不要在起点就加满能够到达终点的油，$

$当然如果加满了油箱都到达不了，那就是无解了，$

$可以的话，输出正好到达所需要的花费即可。：$

if(n==0){	if(1.0*d1/d2>c)	{		printf("No Solution");		return 0;	}	else	{		ans=1.0*d1/d2*p1;		printf("%.2lf",ans);		return 0;	}}

然后就考虑一般的情况了（n>0）

首先要输入所有的站点到原点的距离（这是个坑点）和此站点的油单价；

然后这里我们要注意的是：

如果最后一个站点到起点的距离比终点的距离还大，那我们直接把最后一个站点到起点的距离改成终点距离；

而同理，如果最后一个站点还到达不了终点的话，此时我们就相当于再加一个站点，这个站点也就是终点（便于后面计算）；

然后很明显的一点是，我们从起点到第一个站点，一定需要花费起点的油，所以我们首先给答案加上起点到第一个站点的油费，

当然这里我们也要考虑一下把油箱全都加满能不能从起点到达第一个站点，如果不能，就直接输出无解：

if(1.0*d[1]/d2

然后接下来就是大部分的操作了：

我们定义一个当前花费cost，一个当前油箱中有多少油now，和两个站点之间的距离s，

因为一号站点已经到达，所以我们从二号站点开始遍历，

每次遍历求出两个站点间的距离s　　

然后我们分两种情况来看：

1，之前最小的单价比上一个站点的单价还要小：

那很明显我们还要按照这个之前最小的单价cost来计算，但是这样会出现一个问题，什么问题呢？

我们需要考虑如果我们一直用之前某一个最小的单价的话，那之前那个提供最小单价的站点到当前站点所需要的油量整个油箱能不能装得下，

也就是说，可能会出现到某个时刻邮箱盛满了，但是到不了当前站点。这时候要怎么办呢？

应该不难想到：既然是取最优即最小花费，那我们就用这个最小单价把油箱加满，那么剩下的路程呢？那就只能用上个站点的单价了。

而这种情况还需要进行操作的就是加满之后能到哪里？此时操作一定还未到达当前站点，那我们就把上一个站点的距离加上它加满之后能走的距离，

然后让最小单价cost变成上一个站点的单价，此时循环次数i--，需要重新再从此站点再来一遍。

s=d[i]-d[i-1];//计算两站点距离if(cost

然后就是之前的最小的单价要大于上个站点的单价的情况了，

这种情况要简单一些，此时我们令最小单价cost=上个站点的单价p[i-1],

然后同样的我们来计算从上个站点加满油能否到达此站点，

因为之前已经判断过，上个站点的油费单价已经是最小的了，那如果从上个站点到达此站点，加满油还到不了的话，输出无解；

能到达的话就更新花费ans，注意此时我们也要更新一下当前油箱中的油量now，便于我们继续用这个单价去进行下次操作，看会不会超过油箱容量。

else{	cost=p[i-1];	if(1.0*s/d2<=c)		ans+=1.0*s/d2*cost*1.0;		else	{		printf("No Solution");		return 0;	}	now=1.0*s/d2;}

然后输出最小花费ans就好了，注意保留两位小数。

完整代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n;double d1,c,d2,p1,ans,now,s,cost;double d[8],p[8];bool b;int main(){	scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p1,&n);	if(n==0)	{		if(1.0*d1/d2>c)		{			printf("No Solution");			return 0;		}		else		{			ans=1.0*d1/d2*p1;			printf("%.2lf",ans);			return 0;		}	}	for(int i=1;i<=n;++i)	{		scanf("%lf%lf",&d[i],&p[i]);		if(d[i]>d1) d[i]=d1;		if(i==n&&d[i]