Fuel Economy

题意：
用一辆小破车送牛，两地距离为D，初始油量为B，油箱上线为G，路途有加油站数量为N。
每个加油站有两个参数：
1.距离起始点的距离
2.每升油的价格
问：能否达到目的地，能的话输出最少花费，不能的话输出-1.

思路：
判断是否不能到达，比较简单，即为判断任意两个加油站之间的距离跟最大加油量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;
}