题解：P1016 [NOIP 1999 普及组/提高组] 旅行家的预算

· · 题解

P1016 [NOIP 1999 普及组/提高组] 旅行家的预算 题解

题意解析

给定起点到终点的距离 s、油箱容量 c、每升油能行驶的距离 l、起点油价 p_0 以及 n 个加油站的位置 d_i 和油价 p_i。从空油箱出发，可以中途加油，求到达终点的最小花费，若无法到达则输出 No Solution。

做法

贪心。将终点视为第 n+1 个加油站，距离 s，油价 0。从当前位置出发，在满油可行驶的距离 c \times l 内寻找第一个油价低于当前油价的加油站。如果找到，则加油至恰好能到达该加油站（若当前油量不够则补足）；否则，在可达范围内找油价最低的加油站，加满油后行驶到那里。若可达范围内没有加油站（即无法到达下一站），则输出 No Solution。直到到达为止。

代码

#include<bits/stdc++.h>
using namespace std;

double s,c,l,p0,ans;
int n;
double d[10],p[10];

int main()
{
    cin>>s>>c>>l>>p0>>n;

    if(s==0)
    {
        cout<<"0.00"<<endl;
        return 0;
    }

    for(int i=1; i<=n; i++) cin>>d[i]>>p[i];
    d[0]=0;
    p[0]=p0;
    d[n+1]=s;
    p[n+1]=0;
    n++;
    double o=0;
    double maxd=c*l;
    if(maxd==0)
    {
        cout<<"No Solution"<<endl;
        return 0;
    }

    for(int i=0; i<n; i++)
    {
        if(d[i+1]-d[i]>maxd)
        {
            cout<<"No Solution"<<endl;
            return 0;
        }

        double m=p[i+1];
        int id=i+1;
        for(int j=i+1; j<=n&&d[j]-d[i]<=maxd; j++)
        {
            if(p[j]<p[i])
            {
                id=j;
                m=p[j];
                break;
            }
            if(p[j]<m)
            {
                m=p[j];
                id=j;
            }
        }

        if(m<p[i])
        {
            double f=(d[id]-d[i])/l;
            if(o<f)
            {
                ans+=p[i]*(f-o);
                o=f;
            }
            o-=(d[id]-d[i])/l;
            i=id-1;
        }
        else
        {
            ans+=p[i]*(c-o);
            o=c;
            o-=(d[i+1]-d[i])/l;
        }
    }

    cout<<fixed<<setprecision(2)<<ans<<endl;
    return 0;
}

完

感谢阅读。