旅行家的预算

题目描述

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

输入输出格式

输入格式：

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

接下来有N行。

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

输出格式：

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

输入输出样例

输入样例#1： 

275.6 11.9 27.4 2.8 2102.0 2.9
220.0 2.2

输出样例#1： 

26.95

说明

$N\le 6$ ,其余数字$\le 500$

简单理一下贪心的思想

先确定每个节点间的距离，start为0节点，end为n+1节点。

若存在节点间的距离d[i]-d[i-1]大于D*c，则No Solution；其余情况，必有解。

在每个节点，我们有三种选择：

1.如果指定的goal还未完成，继续行驶；

2.若到达了goal，则向前找第一个邮价比自己低的油站（end处油站油价为0）

i.能够开往（distance<=D*c）,则将goal定为它；

ii不够开往（distance>D*c）,将油加满，将goal定为在加满情况下所能开到的最远油站。

#include<cstdio>#include<iostream>#include<cstring>#include<string>#include<cmath>#include<algorithm>using namespace std;double d[600]={0},p[600];double s,c,D,p1;int n;double money=0,oil=0;double locin(int goal,int now){    if(now==n+1)    {        printf("%.2lf",money);        return 0;    }    if(now<goal)    {        oil-=(d[now+1]-d[now])/D;        locin(goal,now+1);        return 0;    }    if(now==goal)    {        int k=now+1;        while(p[k]>p[now])k++;        if(d[k]-d[now]<=D*c)        {            if(oil<(d[k]-d[now])/D)            {            money+=((d[k]-d[now])/D-oil)*p[now];            oil=(d[k]-d[now])/D;            }            locin(k,now);            return 0;        }        else        {            int w=now+1;            while(d[w]-d[now]<=D*c)w++;            w--;            money+=(c-oil)*p[now];            oil=c;            locin(w,now);            return 0;        }    }}int main(){    cin>>s>>c>>D>>p1>>n;    p[0]=p1;    for(int i=1;i<=n;++i)    {    cin>>d[i]>>p[i];    if(d[i]-d[i-1]>D*c)        {        cout<<"No Solution";        return 0;    }    }    d[n+1]=s;p[n+1]=0;    if(d[n+1]-d[n]>D*c)        {        cout<<"No Solution";        return 0;    }    locin(0,0);    return 0;}