[CSP-J 2023]公路 - 题解

题目大意

一辆车要从第​1个站点到第 ​n 个站点，路程分别为 ​v_1,v_2...v_{n-1} 。每个站点都可以加油，每个站点的加油量为 ​a_1,a_2...a_n ，加 ​1 升油可以前进 ​d 公里。问到达最后一个站点怎样加油最省钱。

思路分析

先看数据范围为 ​10^5 。所以 ​n^2 的做法是不可以的，那么我们可以考虑一下线性的做法。

根据题目中给出的样例及其解释，我们不难发现，每次加油的单价总会低于上一次加油的单价。所以我们可以使用一个小根堆，每到一个站点时，将此站点的单价放入小根堆中。需要加油的时候，访问堆顶元素，将其设置为当前需要加油的单价即为最优。

这里的小根堆我是用的优先队列去实现的。

以下是AC代码，需要注意的是 不要忘记开long long！！！

AC代码

#include<bits/stdc++.h>
#define N 200001
using namespace std;
priority_queue<long long,vector<long long>,greater<long long> >q;
long long n,d,a[N],b[N],c[N],cnt,ans; 
int main(){
	cin>>n>>d;
	for(int i=1;i<n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){ // 最后一个站点油的单价用不到，所以可以不输入 
		cin>>b[i];
	}
	for(int i=1;i<n;i++){
		q.push(b[i]); // 每经过一个站点都要将此站点金额数入队，选出最便宜的价格进行加油 
		long long num=q.top();
		long long numb=a[i]-cnt; // 当前车还可以走多远 
		if(numb<=0){ //处理特殊情况：剩余的油可以直接经过当前站点 
			cnt=cnt-a[i];
			continue;
		}
		cnt=0; // 初始化 
		ans+=(numb)/d*num; // 累加钱数 
		if((numb)%d!=0){ // 处理加油后仍走不到的情况 
			cnt=d-(numb)%d;
			ans+=num;
		}
	}
	cout<<ans;
	return 0;
}

时间复杂度分析

这样的做法只需要循环 ​n-1 次，所以时间复杂度为 ​O(n-1) ，对于 ​100% 的数据是完全可以通过的。