贪心
通过观察题目给出的样例可以发现,本题的贪心策略为:对于第$i$个加油站,其加的油量应为能够使得当前车辆行驶到离当前站最近且油价比当前站低的加油站。因此,需要维护一个数组$nxt$,其中,$nxt[i]$存储每个$a_i$右边第一个比它小的数的下标,如果不存在则置为-1。而维护$nxt$数组则为单调栈的经典应用。
时间复杂度
$O(n)$
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int a[N],n,d;
int nxt[N],q[N],tt;//q为单调栈
LL s[N];//s为每个站点的坐标
int main()
{
cin >> n >> d;
for (int i = 2; i <= n; i ++ )
{
cin >> s[i];
s[i]+=s[i-1];
}
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for(int i=n;i;i--)
{
while(tt&&a[q[tt]]>=a[i]) tt--;
if(!tt) nxt[i]=-1;
else
nxt[i]=q[tt];
q[++tt]=i;
}
LL res=0,oil=0;//oil为当前油量还能行驶的距离
int i=1;
while(i<n)
{
int idx=nxt[i];
if(idx==-1)
{
LL dist=s[n]-s[i];
if(oil>=dist) break;
LL t=(dist-oil+d-1)/d;
res+=t*a[i];
break;
}
LL dist=s[idx]-s[i];
if(oil>=dist)
{
oil-=dist;
continue;
}
LL t=(dist-oil+d-1)/d;
res+=t*a[i];
oil+=t*d-dist;
i=idx;
}
cout << res;
return 0;
}