[CSP-J 2023] 公路 题解

讲解

吐槽：今年T1是最难T1，今年T2是最简单T2。

本题考虑贪心。

贪心策略是：

从站点 $1$ 加油，设想在站点 $1$ 加了无数的油，一直往前开，当开到油价比当前站点低的站点，把之前的多的油卸下来，在这个站点按照之前的策略继续行驶，直到到终点。

我是只顺着遍历，所以时间复杂度是 $O(n)$，期望得分 $100pts$。

注意：这题要加freopen和fclose。

赛时代码：

//O(n)tan xin
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int main(){
	freopen("road.in","r",stdin);
 	freopen("road.out","w",stdout);
	int n,d;
	cin >> n >> d;
	vector<int> v(n-1);
	for (int i=0;i<n-1;++i){
		cin >> v[i];
	}
	vector<int> a(n);
	for (int i=0;i<n;++i){
		cin >> a[i];
	}
	long long ans=0;
	int mn=100000000;
	long long sm=0;//pao le duo yuan
	long double temp=0;//yu xia duo shao sheng
	for (int i=0;i<n-1;++i){
		if (a[i]<mn){//you zui xiao de
			sm-=d*temp;
			long long t=ceil(1.0*sm/d);//duo shao sheng
			temp=t-1.0*sm/d;//hai sheng duo shao
			ans+=t*mn;//da an jia qi lai
			sm=0;
			mn=a[i];
		}
		sm+=v[i];
	}
	sm-=d*temp;
	long long res=ans+ceil(1.0*sm/d)*mn;
	cout<<res<<endl;
 	fclose(stdin);
 	fclose(stdout);
	return 0;
}