P9749 [CSP-J 2023] 公路 题解

此题贪心食用更佳

在输入油价的时候，我们边计算油价的最小值和路程和.

当路程之和 $>0$ 时，计算油价并且减去对应路程即可.

注意事项

要开 $long$ $long$ !!!.

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;

typedef long long ll;
ll n, d, v[100005], a[100005];
ll s = 0, ans;

int main() {
	scanf("%lld%lld", &n, &d);
	for (int i = 1; i < n; i++)
		scanf("%lld", &v[i]);
	ll minn = 2147483640; // 较大的初值
	for (int i = 1; i <= n; i++){
		scanf("%lld", &a[i]);
		s += v[i]; // 计算路程
		minn = min(minn, a[i]); // 较便宜的油价
		if (s > 0) {
			ans += ceil(s * 1.0 / d) * minn; // 油价
			s -= ceil(s * 1.0 / d) * d; // 路程减去对应值
		}
	}
	printf("%lld", ans);
	return 0;
}