[CSP-J 2023] 公路 题解

· · 个人记录

这题就是贪心。首先我们来考虑一个例子：

(d = 1)
   1 -> 2 -> 3 -> 4
v:   1    1    1
a: 2    3    1    1

明显最优的策略是在 1 处买两升油，再在 3 处买一升油到达终点。为什么呢？

在 1 处买两升油明显要优于在 1,2 处各买一升油。所以将这个想法推广就能想到：对于每个被选中需要在这个地方买油的 i，我们需要找到一个最小的 j>i 使得 a_j<a_i，然后在 i 买从 i 到 j 的油（用前缀和维护，将从 1 到 j 的油费向上取整减去从 1 到 i 的油费向上取整），再在 j 处买油，重复上述步骤直到结束。

代码：

#include<iostream>
#define int long long
const int MaxN=1e5+100;
int n,d,v[MaxN]={0},a[MaxN],ans=0;
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin>>n>>d;
    for(int i=1;i<n;i++)std::cin>>v[i],v[i]+=v[i-1];
    for(int i=1;i<=n;i++)std::cin>>a[i];
    for(int i=2,t=1;i<=n;i++){
        if(a[i]<a[t])
            ans+=a[t]*((v[i-1]+d-1)/d-(v[t-1]+d-1)/d),t=i;
        if(i==n)
            ans+=a[t]*((v[i-1]+d-1)/d-(v[t-1]+d-1)/d);
    }
    std::cout<<ans<<std::endl;
}