CSP-J2023公路

发布时间 2023-12-06 09:01:10作者: 陆留生信奥艺术

原题:【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;
}