问题描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）．每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格 Pi(i＝l，2，…N)。
计算结果四舍五入至小数点后两位。
如果无法到达目的地，则输出“No solution”。
INPUT D1＝275.6 C=11.9 D2＝27.4 P=2.8 N=2 油站号i 离出发点的距离Di 每升汽油价格Pi 1 102.0 2.9 2 220.0 2.2
Input
输入文件 D1＝275.6 C=11.9 D2＝27.4 P=2.8 N=2 油站号i 离出发点的距离Di 每升汽油价格Pi 1 102.0 2.9 2 220.0 2.2
Output
输出文件只包含一个整数，表示最少费用
Sample Input
87.75 13.03 5.75 7.29 3
22.10 7.38
24.21 6.81
82.08 6.96
Sample Output
105.95
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=a701
【题解】
设你从当前站加满油能够到达的最远距离为s2;你当前的距离为s1;
如果你能在s1..s2里面找到比当前站s1的油价便宜的最近的站;(如果有的话);
这里;假设不是找离得最近的,比如下图
如果去油价为25的那里,则s2这一段你会需要用油价为100的去跑;
但是如果你先到油价为50的就不一样了;
(这样那段s2你就能用更便宜的油50去跑了);
总之就是先到离当前最近的,价格比当前站便宜的站;
如果在s1..s2找不到比当前油价更低的站;
那么就在这个地方s1加满油(因为在s1..s2区间里面没有比这个站更实惠的油了,那么这一段距离s1..s2就可以用当前站的油去跑,然后在s1..s2里找一个最便宜的站x,特别的,设终点站为n+1它的距离为d1,油价为0);因为如果还想走得更远,就在x站加油;这也是为什么选最便宜的;(当然x..s2这段距离不是用x站的油,而是用s1站的油跑,然后s2之后就用x站的油跑,当然你可能还会在x..s2之间的站里面加油);
按上面这个策略,可以保证你走的每米路,都是用最便宜的油价去走的;
每一段路都是按照最便宜的油价走;那么结果肯定是对的了；
这也是贪心策略;
无解的话,那个“No solution”是“No Solution”;
选比当前站的油价少这一点,没有什么问题;
分割线————
这里我又想了一下;
如果在s1..s2这个区间里面没有比s1站价格小的站;那么在s1加满油然后直接到s1..s2中价格最小的站这个策略是不是对的?
这里101表示的是这个站的价格;
假如101是s1..s2中价格最小的站;因为101>100=s1.price,所以只能在s1加满油,然后到101这个站;
那如果在s1..101所示的站里面还有一个102(也即第二小的站),如果我们选它会出现怎么样的结果?
那样假如我们先选了102然后再选101;
那么经过了x1;我们到102;肯定会把油加满;因为这样才能走得更远;
然后又经过了x2;我们到101;再把油加满;
这样我们在利用s1加满油到了s2之后又可以额外再从s2开始再走x1+x2;
但是s1..s2这个区间我们用的是s1的油;这个是固定没有争议了;
但是x1是用102的油,x2是用101的油;
这就不比直接到101加满油来的优;
因为如果不经过102直接到101加满油;
那么x1+x2这段区间用的油就都是101的油;
这样显然更优;
【完整代码】
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100+10;
struct abc
{
double d,p;
friend bool operator < (abc a,abc b)
{
if (a.d==b.d)
return true;
else
return a.d < b.d;
}
};
double d1,c,d2,p,dis,oil,cost;
abc a[MAXN];
int n,now;
int main()
{
//freopen("F:\rush.txt","r",stdin);
scanf("%lf%lf%lf%lf",&d1,&c,&d2,&p);
scanf("%d",&n);
a[0].d = 0,a[0].p = p;
for (int i = 1;i <= n;i++)
scanf("%lf%lf",&a[i].d,&a[i].p);
sort(a+1,a+1+n);
a[n+1].d = d1,a[n+1].p = 0;
dis = 0,oil = 0,now = 0,cost =0;
while (a[now].d < d1)
{
int f1 = -1;
for (int i = now+1;i <= n;i++)//先找比当前站的价格低的站
if (a[i].p<a[now].p)
{
f1 = i;
break;
}
double tdis = a[now].d + c*d2;
if (f1!=-1 && tdis < a[f1].d) f1 = -1;//如果不在s1..s2里面相当于没找到;
//s2是满油能走到的距离
if (f1==-1)//没找到的话
{
double temp = c-oil;
oil = c;
cost+=temp*a[now].p;
double tp;
for (int i = now+1;i <= n+1;i++)//找在s1..s2里面
if (a[i].d <= tdis)//油价最低的站
{
if (f1==-1)
{
f1 = i;
tp = a[i].p;
}
else
if (a[i].p < tp)
{
tp = a[i].p;
f1 = i;
}
}//else break;is ok
if (f1==n+1)//n+1直接是终点
{
cost-=((tdis-a[f1].d)/d2)*a[now].p;//到终点可能不用满油
printf("%.2lf
",cost);
//cout << cost << endl;
return 0;
}
double need = (a[f1].d-a[now].d)/d2;
oil-=need;//加满了油然后需要减掉到x站的费油
now = f1;
if (f1!=-1)
continue;
}
if (f1==-1)//如果在s1..s2里面没有其他站了,那么就输出无解
{
puts("No Solution");
return 0;
}
//arrive f1.
double need = (a[f1].d-a[now].d)/d2;//找到了s1..s2里面油价更低的站x
if (need <= oil)//x..s2这一段就用x站的油走
{//其实这个时候oil是肯定小于need的;
now = f1;
oil-=need;
}//因为如果没有找到油价比s1更低的,那一段距离s1..s2的油已经有了
//即在s1加满;
//你在s1..s2里面找到了一个油价相对比较低x
//那么从这个x肯定要走到更远的距离>s2
//而你从s1加的油只够你到s2;
//因此need肯定是大于oil的
else
{
double toil = need-oil;
cost += toil*a[now].p;
oil = 0;
now = f1;
}
}
return 0;
}