2024寒假每日一题全部题解传送门>>

分析题意，不管在哪个站点加油，由于每升油所能的行驶的距离都一样，所以在油价尽可能小的站点加油一定会使得最终的花费最小。那么该如何分配呢？

设任意连续$ m $个站点分别为$ x_{i+1},x_{i+2},…,x_{i+m} $，$ x_{i+1} $~$ x_{i+m} $所需要消耗的汽油为$ d $ 升，在每个站点所购买的汽油分别为$ t_{i+1},t_{i+2},…,t_{i+m}$（$ t_{i+1}+t_{i+2}+…+t_{i+m}$=$ d $），且每个站点的油价分别为$ p_{i+1},p_{i+2},…$ $,p_{i+m} $，满足$ p_{i+1}$ $\leq$ $p_k $（$ k=i+2,…,i+m $）。

显然式子$ d * p_{i+1} $ $ \leq $ $ t_{i+1} * p_{i+1} + t_{i+2} * p_{i+2} + … + t_{i+m} * p_{i+m}$一定成立。

那么思路就很清晰了，从当前站点直到油价低于当前站点油价的站点这一段所花费最少的钱就可以利用上述性质来算。上述性质的关键是要算出这一段需要消耗多少汽油。消耗的油量=总距离/每升油行驶的距离，而总距离可以通过预处理前缀和来快速得知，那么接下来就是代码环节啦~

C++代码：

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL v[N], a[N];
int n, d;

int main()
{
    scanf("%d%d", &n, &d);

    for(int i = 1; i <= n - 1; i ++) scanf("%d", &v[i]);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    for(int i = 1; i <= n; i ++) v[i] += v[i - 1]; // 预处理前缀和

    LL res = 0, now = 0; // now表示前汽油量可以行驶的距离
    for(int i = 1; i <= n; i ++)
    {
        int j = i + 1;
        while(j <= n && a[j] >= a[i]) j ++; // 寻找比当前站点油价高的一段

        LL s = v[j - 1] - v[i - 1]; // 从当前站直到油价低于当前站点油价的站点的这一段距离
        LL cnt = (s - now + d - 1) / d; // 需要购买的油量（上取整）

        res += cnt * a[i];
        // 等价于now = cnt*d-(s-now)
        // cnt*d表示购买的总油量所能行驶的总距离，s-now表示加油之前还需要行驶多少距离
        now += cnt * d - s;

        i = j - 1;
    }

    printf("%lld", res);
    return 0;
}