P9749 题解
hn_shw
·
·
题解
首先得先明确一点：如果 a_i>a_j(i<j)，但当前不能买后者。又因为油量无限，想要钱最少，那么我们只需要当发现当前地点的油量比我们在此之前的最便宜油量还要少，那么我们就先结算之前的最便宜油量的 i 到当前点的 j-1 的距离的和，这个和我们可以用一个变量储存，每次加上当前点距离，结算时清零即可，核心代码显而易见：
sum+=a[i];
if(b[i]!=b[i+1]||i==n-1){
int k=0;
if(sum%d!=0) k++;
ans+=(sum/d+k)*b[i];
}
我们又会发现：如果我们结算时买的油所能跑的路程跑完之后超过了当前点，此时我们与下一个点的距离得到缩减，所以如果不处理多出来的答案可能会大！也很简单：
```
sum=-(((sum/d+k)*d)%sum);
```
就是以上这些了，最后贴个全代码：
```
#include<bits/stdc++.h>
using namespace std;
long long a[100005],b[100005];
int main(){
// freopen("road.in","r",stdin);
// freopen("road.out","w",stdout);
int n;
long long ans=0,d;
b[0]=0x3f3f3f3f;
cin>>n>>d;
for(int i=1;i<n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
b[i]=min(b[i],b[i-1]);
}
long long sum=0;
for(int i=1;i<n;i++){
sum+=a[i];
if(b[i]!=b[i+1]||i==n-1){
int k=0;
if(sum%d!=0) k++;
ans+=(sum/d+k)*b[i];
sum=-(((sum/d+k)*d)%sum);
}
}
cout<<ans;
return 0;
}
```