CSP-J2023公路

原题：【23CSPJ普及组】公路(road)

题解：题目提供2个特殊性质，通过这两个性质可以考虑问题的解决方案。

特殊性质 A：站点 1的油价最低。由于题目没有限制邮箱的大小，所以就只要在1站点 加 能恰好开完全程的油就可以了。获分（15分）

特殊性质 B:  由于各个站点的距离恰好是整数升油所能走的倍数，所以用不着考虑走到下一个站点还有多余油该如何处理的问题。获分（15分）

其实特殊性质B，已经在提醒你汽车到达某个站点有多余油该如何处理？

贪心思想是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，如果要得到整个问题的最优答案，那么每一步都要尽可能的得到最优的答案。

本题的贪心思想是：开到第 i （i >= 2）站，总是使用 i 站前面站点的最低油价的站点加油即可。
如何求1--i站的最低加油价格，可以用前缀最小值解决，这个复杂度是O（N）。

根据题目的数据范围可以得知，总路程和花费超出了int类型，所以题目得用long long类型。

本题复杂度是O（N），符合要求。

STD：

#include <bits/stdc++.h>
#define int long long  //宏定义 把以后出现的int 当long long int 使用。
using namespace std;

int a[100005], q[100005], d[100005];  //q[i]数组表示1--i站点之间最低的汽油价格  a[i]第i个站点汽油的单价  d[i]第i站与 i-1 站之间的距离

signed main()  //主函数返回类型不允许用long long int类型。与define同时配对使用
{
	int n, k;
	cin >> n >> k;
	for (int i = 2; i <= n; i++) //从2开始方便理解
		cin >> d[i];
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	q[1] = a[1]; //前缀数组初始化
	for (int i = 2; i <= n; i++)
		q[i] = min(q[i - 1], a[i]);  //最缀最小值
	int s = 0, ans = 0;  //s表示汽车需要行使的里程数  ans表示卖油的钱
	for (int i = 2; i <= n; i++)
	{
		s += d[i];	//开到第i站还有多少公里
		if (s > 0) ans += ceil(s * 1.0 / k) * q[i - 1];  //花费=路程/（每升油能开的里程数）* 每升油的单价
		s -= ceil(s * 1.0 / k) * k;  //把买的油用完，这是离开i站还有多远。要想明白。
	}	
	cout << ans << endl;
	return 0;
}