【普及二】CSP2023-J-2- 公路（ID：19090）
题目描述：
小苞准备开着车沿着公路自驾。公路上一共有n个站点，编号为从1到n。其中站点i与站点i+1的距离为v_i公里。
公路上每个站点都可以加油，编号为i的站点一升油的价格为a_i元，且每个站点只出售整数升的油。
小苞想从站点1开车到站点n，一开始小苞在站点1且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进d公里。问小苞从站点1开到站点n，至少要花多少钱加油？
输入格式：
从文件road.in中读入数据。
输入的第一行包含两个正整数n和d，分别表示公路上站点的数量和车每升油可以前进的距离。
输入的第二行包含n-1个正整数v_1,v_2,…,v_{n-1}，分别表示站点间的距离。
输入的第三行包含n个正整数a_1,a_2,…,a_n，分别表示在不同站点加油的价格。
输出格式：
输出到文件road.out中。
输出一行，仅包含一个正整数，表示从站点1开到站点n，小苞至少要花多少钱加油。
样例输入1：
5 4
10 10 10 10
9 8 9 6 5
样例输出1：
79
样例解释：
最优方案下：小苞在站点1买了3升油，在站点2购买了5升油，在站点4购买了2升油。
数据范围：
对于所有测试数据保证：
1 ≤ n ≤ 10^5
1 ≤ d ≤ 10^5
1 ≤ v_i ≤ 10^5
1 ≤ a_i ≤ 10^5
特殊性质：
A：站点1的油价最低。
B：对于所有1 ≤ i < n，v_i为d的倍数。
测试点分布：
1-5：n ≤ 8
6-10：n ≤ 10^3
11-13：n ≤ 10^5（性质A）
14-16：n ≤ 10^5（性质B）
17-20：n ≤ 10^5（无特殊性质）
一直WA50分！救救孩子吧！
一直WA50分！救救孩子吧！
一直WA50分！救救孩子吧！
我的代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
int n, d, money, s_road;
int v[N];
int a[N];
int main()
{
freopen("road.in", "r", stdin);
freopen("road.out", "w", stdout);
cin >> n >> d;
for (int i = 2; i <= n; i++)
{
cin >> v[i];
v[i] += v[i - 1];
}
for (int i = 1; i <= n; i++)
cin >> a[i];
int cheap = 1;
for (int i = 1; i <= n; i++)
{
if (a[i] < a[cheap])
{
int road = max(0, v[i] - v[cheap] - s_road);
int h_petrol = 0;
h_petrol = (road + d - 1) / d;
money += h_petrol * a[cheap];
s_road = h_petrol * d - road;
if (road == 0)
s_road += abs(v[i] - v[cheap] - s_road);
cheap = i;
}
}
int last_road = max(0, v[n] - v[cheap] - s_road);
int last_h_petrol = (last_road + d - 1) / d;
money += last_h_petrol * a[cheap];
cout << money;
}