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

· · 题解

P1016 旅行家的预算 题解

题目大意

你要从起点开到终点，沿途有若干加油站，每个站油价不同。汽车油箱有容量上限，只能在加油站加油。你希望，如果你能到达终点，所花的钱能最少。

前言

面对题目中有最小或最大的字眼，一般都会考虑贪心，二分等算法。读完题后，我们发现这其实更像一道贪心题，只要保证我能买到的油都是当前状态下最便宜的油，那么如果我能到达终点，钱一定花的最少。对于当前状态，我们作如下解释，顺带解释贪心的正确性。

详细分析及贪心证明

很显而易见的是，我们在每一个加油站选择加油只会有两种情况：

  1. 如果当前的油能到达范围内某个更便宜的车站，那么就刚好加油加到正好能到达那个便宜加油站。
  2. 如果当前的油钱能开到的范围内，不存在更便宜的加油站，那么就在这一站把油加满，再开到最便宜的加油站。

考虑一下这为什么是对的？只要前面有更便宜的，绝不多买当前贵油；没有更便宜时，当前就是最低价，加满最划算，我们做到了每一步都是局部最优。那么后面就是代码实现的问题了，细节较多，具体看代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10;
struct node{
    double d,p;//d为距起点距离，p为油价
};
node a[N];
double s,c,l,p0;//具体含义见题意
int n;
bool cmp(node x,node y){
    return x.d<y.d;//按加油站距离由近到远排序
}
int main(){
    cin>>s>>c>>l>>p0>>n;
    if(s==0){//总路程为0，起点就是终点无需行驶
        cout<<"0.00"<<endl;//花费为0，保留两位小数输出
        return 0;//直接结束程序
    }
    a[0].d=0; a[0].p=p0;//把起点当作第0号加油站，距离0，油价为起点油价
    for(int i=1;i<=n;i++){
        cin>>a[i].d>>a[i].p;
    }
    n++;
    a[n].d=s; a[n].p=0;//虚拟终点，距离为总路程，油价设为0
    sort(a,a+n+1,cmp);//将所有加油站按距离从小到大排序
    double dis=c*l;//计算油箱加满后能行驶的最远距离
    int flag=1;//可达标记，1代表可以到达终点，0代表无法到达
    for(int i=0;i<n;i++){//遍历每两个相邻加油站
        if(a[i+1].d-a[i].d>dis){//相邻站点距离超过最远距离
            flag=0;
            break;//标记不可达，跳出循环
        }
    }
    if(!flag){//判断如果整体不可达
        cout<<"No Solution"<<endl;//输出无解
        return 0;//结束程序
    }
    double oil=0,cost=0;//记录当前油箱剩余油量，总加油花费
    int pos=0;//记录当前所处加油站编号，初始在起点
    while(pos<n){//没到终点就一直行驶
        int firstpos=-1;//记录前方第一个比当前油价便宜的加油站，初始-1未找到
        for(int i=pos+1;i<=n;i++){//遍历当前能到达范围内的所有加油站
            if(a[i].d-a[pos].d>dis) break;//超出续航范围，停止查找
            if(a[i].p<a[pos].p){//找到油价更低的加油站
                firstpos=i;
                break;//记录编号并退出查找
            }
        }
        if(firstpos!=-1){//存在更近且更便宜的加油站
            double oilto=(a[firstpos].d-a[pos].d)/l;//计算前往需油量
            if(oil<oilto){//当前油量不足以开到便宜加油站
                cost+=(oilto-oil)*a[pos].p;//加足够的油，累加花费
                oil=oilto;//更新油箱油量为刚好够用
            }
            oil-=oilto;//行驶消耗对应油量
            pos=firstpos; //更新当前位置到便宜加油站
        }
        else{//范围内没有更便宜的油，当前油价最低
            int minpos=pos+1;//记录范围内油价最低的加油站编号
            for(int i=pos+1;i<=n;i++){//遍历续航范围内所有站点
                if(a[i].d-a[pos].d>dis) break;//超出续航停止
                if(a[i].p<a[minpos].p) minpos=i;//更新最低价站点
            }
            cost+=(c-oil)*a[pos].p;//把油箱加满，累加花费
            oil=c;//油箱设为满油状态
            double oilto=(a[minpos].d-a[pos].d)/l;//开到最低价站需油量
            oil-=oilto;//行驶消耗油量
            pos=minpos;//更新当前位置到最低价加油站
        }
    }
    cout<<fixed<<setprecision(2)<<cost<<endl;//输出最小总花费，保留两位小数
    return 0;
}

以上就是本题全部内容，细节处理好了就没问题。