思路与算法

累计里程除以d向上取整得到截至每段终点必需购买的总升数。新增加的必需升数按此前最低油价计费，无限油箱使其可提前买在该最低价站。

正确性说明

抵达每个前缀终点至少要有ceil(累计距离/d)升，首次变成必需的每升只能在该前缀此前购买，因此代价至少为此前最低价。把该升提前在最低价站购买满足所有前缀油量约束，故这些逐升下界可同时达到。

复杂度

O(n)时间、O(n)输入存储；累计里程、油量及费用用64位，初始化与前缀扫描均线性。

易错点

只出售整数升，必须对累计里程而非每段分别向上取整；到终点无需再买油，n=1费用0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    long long d;
    cin >> n >> d;
    vector<long long> v(n - 1), a(n);
    for (auto &x : v)
        cin >> x;
    for (auto &x : a)
        cin >> x;
    long long dist = 0, bought = 0, price = LLONG_MAX, ans = 0;
    for (int i = 0; i < n - 1; i++) {
        price = min(price, a[i]);
        dist += v[i];
        long long required = (dist + d - 1) / d;
        ans += (required - bought) * price;
        bought = required;
    }
    cout << ans << "\n";
}