AcWing 5308. 公路
原题链接
中等
作者:
假如有点困
,
2024-10-09 13:18:28
,
所有人可见
,
阅读 8
#include<iostream>
#define int long long
using namespace std;
const int N = 1e5+10;
int v[N],a[N],s[N],c[N];
signed main()
{
int n,d;
cin>>n>>d;
for(int i=1;i<n;i++) cin>>v[i];//每i的距离
for(int i=1;i<=n;i++) cin>>a[i];//第i号站点的油价
for(int i=1;i<n;i++){
s[i]=s[i-1]+v[i];//从起点i+1个站点的路径之和
c[i]=(s[i]+d-1)/d;//从起点到第i+1个站点的总油耗
}
int price=a[1];//第一个站点必须加油,所以记录第一个站点的价格
int cost=0;//总共花费多少钱
for(int i=1;i<n;i++){
cost+=(c[i]-c[i-1])*price;//记录每一段的花费
price=min(price,a[i+1]);
}
cout<<cost;
return 0;
}