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;
}