4471: 公路 [CSP-J 2023]
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：3
题目描述
小苞准备开着车沿着公路自驾。
公路上一共有 个站点，编号为从 到 。其中站点 与站点 的距离为 公里。
公路上每个站点都可以加油，编号为 的站点一升油的价格为 元，且每个站点只出售整数升的油。
小苞想从站点 开车到站点 ，一开始小苞在站点 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 公里。问小苞从站点 开到站点 ，至少要花多少钱加油？
输入
输入的第一行包含两个正整数 和 ，分别表示公路上站点的数量和车每升油可以前进的距离。
输入的第二行包含 个正整数 ，分别表示站点间的距离。
输入的第三行包含 个正整数 ，分别表示在不同站点加油的价格。
输出
输出一行，仅包含一个正整数，表示从站点 开到站点 ，小苞至少要花多少钱加油。
样例输入 复制
5 4
10 10 10 10
9 8 9 6 5样例输出 复制
79提示
【样例 1 解释】
最优方案下：小苞在站点 买了 升油，在站点 购买了 升油，在站点 购买了 升油。
【样例 2】
见选手目录下的 road/road2.in 与 road/road2.ans。
【数据范围】
对于所有测试数据保证：，，，。
| 测试点 | 特殊性质 | |
|---|---|---|
| 无 | ||
| 无 | ||
| A | ||
| B | ||
| 无 |
- 特殊性质 A：站点 的油价最低。
- 特殊性质 B：对于所有 ， 为 的倍数。
#include<bits/stdc++.h>
using namespace std;
/*解法：贪心+模拟-时间复杂度-O(n)-100pts*/
const long long N = 1e5 + 10;
long long s[N];//距离的前缀和数组-用于求解任意两点间的距离
long long p[N];//每个站点对应的油价price
int main() {
long long n, d; cin >> n >> d;
for (long long i = 2; i <= n; i++) {
long long v; cin >> v;
s[i] = s[i - 1] + v;//预处理距离的前缀和
}
for (long long i = 1; i <= n; i++) cin >> p[i];
//处理油价的降序序列
vector<long long> ds; ds.push_back(1);
long long minv = p[1];
for (long long i = 2; i <= n; i++) {
if (p[i] < minv) {
minv = p[i];
ds.push_back(i);
}
}
if (ds[ds.size() - 1] != n) ds.push_back(n);
long long l_dist = 0/*剩余距离*/, ans = 0;
//沿着油价的降序序列进行贪心+模拟
for (long long i=0; i < ds.size() - 1; i++) {
long long r_dist = s[ds[i + 1]] - s[ds[i]];//相邻两点间的距离
if (r_dist < l_dist) l_dist -= r_dist;
else {
r_dist -= l_dist;
long long nums = ceil(r_dist * 1.0 / d);//针对当前距离需要买多少升油
ans += p[ds[i]] * nums;
l_dist = nums * d - r_dist;
}
}
cout << ans << endl;
return 0;
}