直接贪心+前缀和,写了一个小时才把思路+代码+坑全部过完
一开始还想记录下标,弄个哈希+排序的哈哈
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
LL n,d;cin>>n>>d;
vector<pair<LL,LL>> v(n);
vector<LL> a(n+1);
LL res=0; //当前车所在的位置,一开始是0
LL price=v[0].second; //以及当前位置油的价钱
LL sum=0; //需要的车钱
LL o=0; //自身目前存储的油可以用来行驶的距离
LL k=n-1;
for(LL i=0;i<n;i++)
{
if(i==0)
continue;
cin>>v[i].first;
}
for(LL i=0;i<n;i++)
cin>>v[i].second;
for(LL i=1;i<n+1;i++)
a[i]=a[i-1]+v[i-1].first; //计算前缀和数组
for(LL i=1;i<v.size();i++)
{
if(v[i].second>price)
{
//这里跳过要注意,前提是你的当前油量够达到下一个目的地,否则就必须停在这里买油了
k=0;
continue;
}
//下面计算两地的路程所需要的油,可以用前缀和来进行优化.通过路程除以d的向上取整计算
LL need=(a[i+1]-a[res+1]-o+d-1)/d; //减去当前的油可以行驶的距离
sum=sum+need*v[res].second;
o=o+need*d;
//下面更新res和price
price=v[i].second; //这里要注意一个东西,就是它可能并不需要一定买need油,因为自身可能还剩下一些油足以让他
//到达下一个站点
o-=a[i+1]-a[res+1];
res=i;
k=n-1;
}
if(k!=n-1)
{
long long need=(a[n]-a[res+1]-o+d-1)/d; //可能需要再加上一次这个操作
sum=sum+need*v[res].second;
}
cout<<sum<<endl;
return 0;
}
后面的思路对了之后,碰到了两个坑,一个用o来解决,因为可能并不需要多买一些油,可能自身的油还有些,买少一点,花的钱可以更少,第二个坑就是可能一直在continue,固然需要对其进行一次检查,防止没有从res位置跳到n位置。如果是==n-1的话(这里可以将k设置成布尔值其实)
就说明他是跳到最后一次位置了的.固然不用多加即可