思路很简单:从当前加油站开始往下走,如果有加油站比当前便宜,就加上走过的路程,如果当前更便宜,就接着往下走,直到遇到更便宜的
oil变量用来记录之前加油向上取整后剩余的
代码贴在下面:
#include<bits/stdc++.h>
using namespace std;
struct node
{
long long i;
long long v;
long long a;
};
const int maxn=100005;
node a[maxn];
long long n;
long long d;
long long ans=0;
double oil=0;
signed main()
{
cin>>n>>d;
for(int i=1;i<n;i++)
{
cin>>a[i].v;
}
a[n].v=0;
for(int i=1;i<=n;i++)
{
cin>>a[i].a;
}
long long minmoney=a[1].a;
long long s=a[1].v;
long long b=0;
/*for(int i=1;i<=n;i++)
{
cout<<a[i].v<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++)
{
cout<<a[i].a<<" ";
}
cout<<"\n";*/
for(int i=2;i<=n;i++)
{
if(minmoney>a[i].a)
{
oil+=ceil(1.0*s/d)-1.0*s/d;
//cout<<oil<<"\n";
ans+=int(ceil(ceil(1.0*s/d)-oil))*minmoney;
minmoney=a[i].a;
s=a[i].v;
//b=1;
}
else
{
s+=a[i].v;
}
//cout<<minmoney<<" "<<s<<" "<<ans<<" "<<b<<"\n";
}
cout<<ans<<"\n";
return 0;
}