P1016 [NOIP1999 提高组] 旅行家的预算

题目描述

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

输入格式

第一行，�1D1​，�C，�2D2​，�P，�N。

接下来有 �N 行。

第 �+1i+1 行，两个数字，油站 �i 离出发点的距离 ��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

说明/提示

�≤6N≤6，其余数字≤500≤500。

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

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

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

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

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

AC代码：

#include<bits/stdc++.h>
using namespace std;
double maxx,mo=0,d2,temlen=0,d1,c,p;
//temlen：油箱中在到达了下一个加油站时油箱中的剩余油量可以继续走的路程
int n;
struct add
{
    double co;
    double dis;
}pl[10000];//加油站结构体：dis-距离起点的距离，co：油价
int move(int now)//1.now:现在到达的加油站
{
    int can=99999;
    int f=pl[now].dis;
    for(int i=now+1;i<=n&&pl[i].dis-f<=maxx;i++)
    {
        if(pl[i].co<pl[now].co)//2.
        {
            mo+=((pl[i].dis-f-temlen)/d2)*pl[now].co;
            temlen=0;
            return i;
        }
        if(can==99999||pl[i].co<pl[can].co)can=i;
    }
    if(d1-pl[now].dis<=maxx)
        {
            mo+=((d1-pl[now].dis-temlen)/d2)*pl[now].co;
            return 9999;
        }
    if(can==99999)//4.
    {
        cout<<"No Solution";
        return -1;
    }
    else//3.
    {
        mo+=c*pl[now].co;
        temlen+=(maxx-pl[can].dis+f);
        return can;
    }
}
int cmp(add a,add b)
{
    return a.dis<b.dis;
}
int main()
{
    cin>>d1>>c>>d2>>p>>n;
    pl[0].dis=0;
    pl[0].co=p;
    for(int i=1;i<=n;i++)cin>>pl[i].dis>>pl[i].co;
    sort(pl,pl+n,cmp);
    maxx=c*d2;
    int k=0,t;
    do
    {
        t=move(k);
        k=t;
        if(t==-1)return 0;
    }while(t!=9999);
    printf("%.2f",mo);
    return 0;
}