公路 (CSP-J 2023)

这是个调度的题，一般考虑找贪心算法。小苞肯定希望加便宜的油，所以每次加到便宜的油的时候，能开越远越好，那需要开多远呢？我们观察可以发现，他希望开到下一个有更便宜的油的地方。

所以，贪心算法就是：从第一个数开始，找一个单调下降的序列，每次加油要正好可以开到下一个数所在在位置。这个“单调下降”序列可以计算出来存在一个数组里，或者也可以直接滚动计算（像下面程序这样），找到下一个更便宜的油的时候，再回去计算上个加油站应该要加多少油。

有一个小麻烦是油只能加整数升，但是剩下的油可以是小数的，需要想一个办法处理防止浮点数不准确的问题。我们看是否能转化成整数处理，发现如果我们记录油还能走的距离，就可以不用浮点数了，也就是下面程序中的D。另外，注意需要long long。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n,d;
int v[100005];
int a[100005];
ll ans;
 
int x;   // current best price, decreasing
ll D;    // distance to travel
 
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]);
    }
 
    x = a[1];
    for (int i = 2; i <= n; i++) {
        D += v[i-1];
        if (a[i] < x || i == n) {
            if (D > 0) {
                ll amt = (D + d - 1) / d;   // integer ceil
                ans += amt * x;
                D -= amt * d;   // possibly negative
            }
            x = a[i];
        }
    }
    printf("%lld", ans);
    return 0;
}