题号 NC24408
名称 Fuel Economy
来源 USACO英文版-2013 Open Contest-Silver
每日一题三期汇总贴~


如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：Dream_coding
思路：
判断是否不能到达，比较简单，即为判断任意两个加油站之间的距离跟最大加油量G之间的关系（最终位置也算一个加油站点）。到第一个加油站要看初始油量B（特判）。

然后就是能到达的情况下，我们如何使得花费最少。那么我们思考，每到一个加油站，我们是不是要考虑要不要加油呢？如果我车子的剩余油量足够我跑到往后最近的比我当前加油站便宜的那个加油站，那我肯定跑到那个车站在加油啊（中间车站我只是路过看看，太贵了！！！）
但如果不够呢?那么我么肯定要加油喽。在哪加油呢？
我们处理这样的一个数组，bb[]，表示比当前加油站价格便宜的距离我最近的那个加油站的下标，
意思是什么呢？
1 2 3 4 n+1
eg：5 6 7 2 5//表示加油站的价格
4 4 4 5
那么我现在如果在1号加油站，我肯定是跑到4号加油站最加油最便宜，如果到不了，我只好在当前加油站加油最划算。
1.如果最大油量G---我加点油或者加满能够到4号那个地方，我肯定少加让刚好够我到4号那个加油站就好了
2.我加满了都到不了4号，那目前就是我当前加油站最便宜了（往后价格为6,7,都贵）那么我就在当前加油站加满。接着往后跑。

途中我是一直在耗油的，不管我是路过这个加油站，还是停下来加油了。所以每次循环我要更新剩余油量。

#include<bits/stdc++.h>

#define maxn 50010

using namespace std;
typedef long long ll;

int n,g,b,d;
ll ans=0;

struct node{
    int x;//距离
    int y;//价格
}a[maxn];

int bb[maxn];

int cmpp(node a,node b){//不知道距离是否有序，按照从小到大排列
    return a.x < b.x;
}
void init(){//记录当前加油站往后的第一个油价比当前加油站低的加油站的下标 
      bb[n] = n+1;
      int i,j;
      for(i=n-1;i>=1;i--){
           for(j=i+1;j!=n+1 && a[i].y <= a[j].y;j=bb[j]);
            bb[i] = j; 
      } 
}

void solve(){
     b-= (a[1].x-a[0].x);//到达第一个加油站的剩余油量 
     for(int i=1;i<=n;i++){//先判断当前加油站是否要加油，然后往下一个车站走 
        if(b < (a[bb[i]].x - a[i].x)){
            if(g >= a[bb[i]].x - a[i].x){
            ans += a[i].y * (a[bb[i]].x-a[i].x-b);
            b = a[bb[i]].x-a[i].x;//油量更新为刚好够到达 
            }
            else{
             ans += a[i].y*(g-b);
             b = g;    
            }
        }
        b-= a[i+1].x-a[i].x;
    }
}

int main(){
    cin>>n>>g>>b>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    a[0].x = 0;//把初始位置跟终点也当做加油站给放进去 
    a[n+1].x = d;
    sort(a+1,a+n+1,cmpp);
    if(b < a[0].x){cout<<"-1"<<endl;return 0;}//当前油量不支持达到第一个加油站 
    for(int i=2;i<=n+1;i++){//如果任意两个加油站距离大于油箱上限，即为不可到达
        if(a[i].x - a[i-1].x > g){
            cout<<"-1"<<endl;
            return 0;
        }
    }
    init();
    solve();
    cout<<ans<<endl; 
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目5月4日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴