题目描述

小苞准备开着车沿着公路自驾。

公路上一共有 n个站点，编号为从 1 到 n。

其中站点 i与站点 i+1 的距离为 vi公里。

公路上每个站点都可以加油，编号为 i的站点一升油的价格为 ai元，且每个站点只出售整数升的油。

小苞想从站点 1开车到站点 n，一开始小苞在站点 1且车的油箱是空的。

已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 d公里。

问小苞从站点 1开到站点 n，至少要花多少钱加油？

输入格式

输入的第一行包含两个正整数 n和 d，分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 n−1个正整数 v1,v2…vn−1，分别表示站点间的距离。

输入的第三行包含 n个正整数 a1,a2…an，分别表示在不同站点加油的价格。

输出格式

输出一行，仅包含一个正整数，表示从站点 1开到站点 n，小苞至少要花多少钱加油。

数据范围

对于所有测试数据保证：1≤n≤105，1≤d≤105，1≤vi≤105，1≤ai≤105。

特殊性质 A：站点 1的油价最低。

特殊性质 B：对于所有 1≤i<n，vi 为 d的倍数。

输入样例

5 4
10 10 10 10
9 8 9 6 5

输出样例

79

样例解释

最优方案下：小苞在站点 1买了 3 升油，在站点 2 购买了 5 升油，在站点 4 购买了 2 升油。

贪心模拟思路分析：

1.第一个站点必然要加油，最后一个站点必然不用加油，w[n]=-1.

2.用单调栈实现nxt[]：对于每个要加油的站点，找到下一个加油费用比当前加油站点加油费用小的站点（贪心）。

3.贪心模拟

4.注意数据范围，开long long.

C++ 代码

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

typedef long long LL;

const int N=1e5+6;
int n,d;
LL w[N];    //第i个站点的油价
int nxt[N]; //nxt[i]: 第i个站点到下一个油钱比它小的站点的 站点下标 
LL sum[N];  //1到i站点的路程 

int main() {

    cin>>n>>d;
    for(int i=2;i<=n;i++) {
        LL x;
        cin>>x;
        sum[i]=sum[i-1]+x;
    }
    for(int i=1;i<=n;i++) cin>>w[i];

    //单调栈：存储下标 
    stack<int> stk;
    w[n]=-1; //要赋值为最小油价 
    for(int i=1;i<=n;i++) {
        while(!stk.empty()&&w[i]<w[stk.top()]) {
            nxt[stk.top()]=i;
            stk.pop();
        }
        stk.push(i);
    }
    nxt[n]=n+1;

    LL res=0;
    LL has_x=0; //已经走的路程 
    for(int i=1;i<=n-1;i=nxt[i]) {
        int to=nxt[i];
        LL num=ceil(double(sum[to]-has_x)/d);
        res+=(w[i]*num);
        LL s=d*num;
        has_x+=s;
    }

    cout<<res<<'\n';

    return 0;
}