题解 P1016 【旅行家的预算】

· · 题解

传送门(P1016)

我这题是写给像我这样的蒟蒻看的，顺便加强一下我对这题的理解。

dalao们看了勿喷

这个题是一个贪心题，外加模拟。。

一开始我想简单了。

当时认为，只要从当前位置往后找一个最便宜的加油站（在当前位置能走到的最远距离内），然后把油加到刚刚能走到这个加油站，再继续找就行了。

(我想应该有像我这样想的)

如果设当前所在加油站距出发点距离为x1, 费用为p1，后面最便宜的加油站距出发点距离设为x2

那么费用为 (x2-x1)/d2*p1 (d2就是题目中的d2)

然后从当前位置跳过去继续找就行了

但是，这样交上去，会WA一个点，只得75分...QnQ

（看得出，洛谷样例有些H2O啊）

其实呢，这个题有一个略微坑人的情况，像下面这张图

这种情况就要在当前处直接把油加满。

为什么呢？

显而易见，若按照上面的做法做的话，在pi处到maxs处所用的油是在pi处加的。但是如果在pi到maxs处用p1处加的油，费用显然更低。

这就要额外储存剩余的油量sh

（不要因为变量名打我）逃

这样 在没有特殊情况时 公式就变成了((x2-x1)/d2-sh)*p1

每次找出后面油费最小的加油站,都要判断一下

至于No Solution,我想说了这么多,再加上之前有多位大佬解释,因该知道咋做了

看看当前能走到的最远距离内有木有加油站就行了

总结

1.先枚举在范围内的加油站,找出花费最小的加油站

2.如果在范围内没找到加油站，就输出 No Solution

3.将 这个加油站 与 当前所在的加油站 的油费比较一下

4.如果 当前所在的加油站 费用更低，就直接加满油，然后开车到后面找出的最便宜的加油站，用sh储存一下剩余的油量；反之，就只把油加到刚刚能开到后面这个加油站，sh变为0

5.如果从当前这个加油站能直接开往终点，就把油加到刚刚能开到终点，输出price即可

如果已经懂了的话,就不要往下翻了(下面是代码),自己试着做做吧!

上我丑陋的代码...

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define inf 99999
using namespace std;
int n;
double price=0,d1,d2,c,p1,maxs;
struct jia{
    double pn;
    double dn;
}z[7];
bool cmp(jia x,jia y)
{
    return x.dn<y.dn;
}
void start(int now,double sh)            //now是目前所在的加油站的序号 
{                                        //sh就是题解上的sh... 
    int minn;
    double minp=inf;
    for(int i=now+1;i<=n;i++)
    {
        if(z[i].dn>z[now].dn+maxs)      //判断,如果第i个加油站在当前位置加满油也走不到,就break  
            break;
        if(z[i].pn<minp)
        {
            minp=z[i].pn;
            minn=i;
        }
    }
    if(z[now].pn<=minp&&z[now].dn+maxs>=d1) //判断是否有解 
    {
        price+=((d1-z[now].dn)/d2-sh)*z[now].pn;
        printf("%.2lf\n",price);
        exit(0);
    }
    if(minp==inf)                      //如果在能走到的范围内没有加油站 
    {
        printf("No Solution\n");
        exit(0);
    }
    if(z[now].pn<minp)                //当前位置的加油站油费 < 后面找到的最便宜的加油站的油费 
    {
            price+=(c-sh)*z[now].pn;
            sh=c-(z[minn].dn-z[now].dn)/d2;
    }   
    else{                            //反之 
        price+=((z[minn].dn-z[now].dn)/d2-sh)*z[now].pn;
        sh=0.0;
    }
    start(minn,sh);
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>d1>>c>>d2>>p1>>n;
    z[0].dn=0;                      //这里我把起始点的加油站存到了z[0]里  
    z[0].pn=p1;
    for(int i=1;i<=n;i++)
        cin>>z[i].dn>>z[i].pn;
    maxs=c*d2;                     //预先算出最大油量所能走到的最远距离  
    sort(z+1,z+n+1,cmp);
    start(0,0.0);                  //开始了"主"程序 ... 
    return 0;
}

欢迎各位dalao前来指正不足

我会给dalao设上牌位供奉的 orz orz（逃）~~

打了一个半小时（本人打字速度堪称蜗牛）支持一下呗