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

· · 题解

P1016

大意

一个人开车从一个城市去另一个城市，出发时油箱是空的。已知两个城市距离、油箱容量、每升油能跑多远、起点的油价，还有沿途 N 个加油站的位置和各自的油价。
问：怎么加油最省钱，算出最少要花多少钱。如果根本开不到终点，就输出 No Solution。

思路

贪心，能省就省。

站在当前加油站，往前看：

前面有更便宜的油：就加刚好够开到那的油，到那再加便宜的。

前面都比这贵：那就在这把油加满，然后开到前面最便宜的那个站再加油。

重复上面的，直到开到终点，中途判断一下会不会到不了终点。

具体实现看代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=507;
const double inf=0x3f3f3f3f;
struct node{
    double l,p;
}a[maxn];
bool cmp(node x,node y){
    return x.l < y.l;
}
int main(){
    double s,c,l,p0;
    int n;
    cin>>s>>c>>l>>p0>>n;
    a[0].l=0;
    a[0].p=p0;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].p;
    }
    a[n+1].l=s,a[n+1].p=0;
    sort(a,a+n+2,cmp);
    double mr=c*l; //满油能跑多远
    double nr=0; //当前油量
    double cost=0; //花了几个钱
    int now=0; //当前在第几个站
    bool ok=1;//是否能到终点
    if(s==0.00){
        cout<<"0.00";//特判
        return 0;
    }
    //找第一个比当前便宜的油站:
    while(now <= n){
        int nt=-1;
        for(int i=now+1;i<=n+1;i++){
            double d=a[i].l-a[now].l;
            if(d > mr) break;
            if(a[i].p < a[now].p){
                nt=i;
                break;
            }
        }
        //如果找不到更便宜的，就找范围内最便宜的:
        if(nt == -1){
            double mp=1e18;
            for(int i=now+1;i<=n+1;i++){
                double d=a[i].l-a[now].l;
                if(d > mr) break;
                if(a[i].p < mp){
                    mp=a[i].p;
                    nt=i;
                }
            }
        }
        //一个站都到不了，无解
        if(nt==-1){
            ok=0;
            break;
        }
        //计算开到下一站需要多少油
        double nd=(a[nt].l-a[now].l)/l;
        //决定加多少油:
        if(a[nt].p < a[now].p){
            //1.下一站更便宜 加刚好到下一站的油
            if(nr < nd){
                cost+=(nd-nr)*a[now].p;
                nr=nd;
            }
        }
        //2.下一站更贵 加满
        else {
            cost+=(c-nr)*a[now].p;
            nr=c;
        }
        nr-=nd;
        now=nt;
    }
    if(!ok) cout<<"No Solution";
    else cout<<fixed<<setprecision(2)<<cost;
    return 0;
}