【每日一题】Fuel Economy

题意：

一辆车的油箱容量为G(1<=G<=1e6), 车每移动一个单位的距离就要消耗一个单位的油，总共需要走D个单位的距离(1<=D<=1e9)。
除此之外，路上一共有N个加油站，第i个加油站与起点的距离为Xi(0<=Xi<=D)，每单位油的价格为Yi(1<=Yi<=1e6)。
一开始你的油箱中有B个单位的油(0<=B<=D)，请计算出到达目的地时花费的油费用的最小值。如果无法到达目的地，那么输出-1。

分析：

首先按加油站离起点的距离从小到大排序，那么离起点最近的加油站称为1号加油站，离起点第二近的加油站称为2号加油站，以此类推。
接着用rr[i]表示右边第一个比i号加油站汽油单价小的加油站的下标，rr数组可以使用一个单调栈预处理出来。
接下来进行如下贪心：
使用i从左到右遍历，i为当前的加油站，设b为当前剩余的汽油量，如果b大于等于i号加油站到rr[i]号加油站的距离，则我们可以开车到rr[i]号加油站再加油，这样更赚，因此我们此时不加油；如果b小于i号加油站到rr[i]号加油站的距离，我们继续分类讨论：若我们能把当前汽油加到能正好到rr[i]号加油站，我们就进行这样的加油，到了rr[i]号加油站后再进行后续的加油，这样更赚；若因为油箱大小的限制使得我们无法把汽油加到能正好到rr[i]号加油站，我们索性就把油加满，因为[i,rr[i]-1]区间的汽油单价里，i号加油站的是最小的，因此在此处加满油是最赚的。

代码：

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

struct node
{
    int x,y;
}R[50005];
bool cmp(node a,node b)
{
    return a.x<b.x;
}
int rr[50005];
int main()
{
    int i,j,n,g,b,d;
    long long ans=0;
    scanf("%d%d%d%d",&n,&g,&b,&d);
    for(i=1;i<=n;i++)scanf("%d%d",&R[i].x,&R[i].y);
    sort(R+1,R+1+n,cmp),R[n+1].x=d,R[0].x=0;
    rr[n]=n+1;
    for(i=n-1;i>=1;i--)
    {
        for(j=i+1;j!=n+1&&R[i].y<=R[j].y;j=rr[j]);
        rr[i]=j;
    }
    for(i=0;i<=n;b-=R[i+1].x-R[i].x,i++)
    {
        if(g<R[i+1].x-R[i].x){printf("-1\n");return 0;}
        if(!i)continue;
        if(b<R[rr[i]].x-R[i].x)
        {
            if(g>=R[rr[i]].x-R[i].x)ans+=(long long)R[i].y*(R[rr[i]].x-R[i].x-b),b=R[rr[i]].x-R[i].x;
            else ans+=(long long)R[i].y*(g-b),b=g;
        }
    }
    printf("%lld\n",ans);
    return 0;
}