[CSP-J 2023] 公路 题解
2023-11-19 13:59:24
发布于:四川
243阅读
0回复
0点赞
讲解
吐槽:今年T1是最难T1,今年T2是最简单T2。
本题考虑贪心。
贪心策略是:
从站点 加油,设想在站点 加了无数的油,一直往前开,当开到油价比当前站点低的站点,把之前的多的油卸下来,在这个站点按照之前的策略继续行驶,直到到终点。
我是只顺着遍历,所以时间复杂度是 ,期望得分 。
注意:这题要加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;
}
全部评论 2
5天前 来自 浙江
02024-08-31 来自 上海
0
有帮助,赞一个