CSP-J 2023 T1小苹果 T2公路-[CSP-J 2023] T2 - 公路

本题的油箱无限大，所以当一个点的油价很便宜时，我们要在这个点买足够多的油，这个足够多的限制在哪里？就是能够支撑我们到下一个更便宜的点。至此思路就很明显了，在起点处是必须要买油的，当遇到一个比起点更低价格的点时，计算这两个点之间的距离（前缀和），用起点的价格买足够多的油，来到这个点之后继续向后寻找更便宜的油。

要注意的点是买的油一定是整数，例如点$1$与点$2$的距离是$10$，每升油能让我们走$4$，在起点处就必须买$3$升油（$3\ast 4=12>10$）如果点$1$与点$2$的距离是$12$，我们还是需要买$3$升油，所以要买的油的数量$x$与距离$distance$的关系是$x=\lceil \frac{distance}{d}\rceil$，具体写代码时，为了避免浮点数或者取整操作，我们可以使$x=\frac{distance+d-1}{d}$，这个式子和上式是等价的，例如$\frac{10+4-1}{4}=3$，$\frac{12+4-1}{4}=3$。另外，到达点$2$之后我们还剩$2$升油，这$2$升油是可以继续用的。

最终车一定要开到$n$号点，所以如果在最后一个点时没有更新更便宜的油价，那么终点到上一个便宜点之间的距离是会被忽略的。所以最后要加一下开到终点的花费。

#include <bits/stdc++.h>
#define A 100010

using namespace std;
typedef long long ll;
int n, v[A], a[A];
ll ans, d, sum[A];

int main(int argc, char const *argv[]) {
	cin >> n >> d;
	for (int i = 2; i <= n; i++) {
		scanf("%d", &v[i]);
		sum[i] = sum[i - 1] + v[i];
	}
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int pos = 1;
	ll oil = 0, leftoil = 0, minn = a[1];
	for (int i = 2; i <= n; i++) {
		if (a[i] < minn) {
			oil = (sum[i] - sum[pos] - leftoil + d - 1) / d;
			leftoil += oil * d - (sum[i] - sum[pos]);
			ans += oil * minn;
			minn = a[i];
			pos = i;
		}
	}
	ans += (sum[n] - sum[pos] - leftoil + d - 1) / d * minn;
	cout << ans << endl;
}

由于做法中出现了乘法，所以代码写出之后需要关注一下是否会爆$int$，每个变量的数据范围都是$1e5$，前缀和$sum[n]=n\ast v[i]=1e10$会爆$int$，$oil\ast d$和$oil\ast minn$也有可能爆$int$，需要给相应的变量开上$longlong$。