【每日一题】2021年4月27日题目 Fuel Economy

题号 NC24408
名称 Fuel Economy
来源 USACO英文版-2013 Open Contest-Silver

题目描述

在一个一位数轴上有个加油站，富坚开始时在坐标为0位置，他要开车到坐标为d的位置，车每行驶一个单位就消耗一个单位的油。

车的油箱最大容量为,初始时油箱中有单位的油。很明显油量为0的时候就不能行驶了，所以富坚需要在中途的加油站中加油，

对于第个加油站其每单位油需要元，问富坚最少需要花费多少才能到达目的地？

样例

输入

4 10 3 17
2 40
9 15
5 7
10 12

输出

174

算法1

(贪心 + 单调栈)

分析：

我们每到一个加油站考虑的只有加油还是不加油，如果加油要加多少？

如果我们在油的容量允许的情况下往后走到一个最近的价格比当前的加油站便宜的加油站

那么我们当然是在当前加油站加到恰好能走到的油量后，再进行下一次决策是最好的

单调栈

找到第一个比当前加油站便宜的加油站的位置我们可以从后往前用单调栈来维护

贪心：

1. 如果车的容量能走到比当前加油站价格更便宜的加油站，那么就将油加到恰好能走到的油量即可
2. 否则就将油量加满（因为后续不加油的情况下能走到的加油站都是比当前加油站价格高的）

细节：
1.每一个加油站不管有没有加油都需要访问一次，避免疏漏了更优的决策
2.将终点作为一个哨兵加入到序列中更方便求解

时间复杂度

参考文献 https://blog.nowcoder.net/n/9ec1142c6c2244aab7f0a377f1fbcd56

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 500010;
typedef pair<int,int> PII;
typedef long long LL;
int stk[N],tt,r[N];
int n,g,b,d;
PII station[N];

int main()
{
    scanf("%d%d%d%d",&n,&g,&b,&d);
    for(int i = 1;i <= n;i ++) scanf("%d%d",&station[i].first,&station[i].second);
    station[n + 1] = make_pair(d,0);
    n = n + 1;
    sort(station + 1,station + 1 + n);
    for(int i = n;i >= 1;i --)
    {
        while(tt && station[stk[tt]].second >= station[i].second) tt --;
        if(tt) r[i] = stk[tt];
        stk[++ tt] = i;
    }
    LL res = 0;
    for(int i = 1;i < n;i ++ )
    {
        b -= station[i].first;
        if(b < 0) 
        {
            puts("-1");
            return 0;
        }
        if(b < station[r[i]].first - station[i].first)
        {
            if(g >= station[r[i]].first - station[i].first)
            {
                res += 1ll * (station[r[i]].first - station[i].first - b) * station[i].second;
                b = station[r[i]].first - station[i].first;
            }else
            {
                res += 1ll * (g - b) * station[i].second;
                b = g;
            }
        }
        b += station[i].first;
    }
    printf("%lld\n",res);
    return 0;
}