题解 P9749 [CSP-J 2023] 公路

· · 题解

思维好题。

思路

以下为考场思路。

读题，有几个关键元素。

  1. 两点间的路程。
  2. 每个点的油价。
  3. 每升油能前进的路程。
  4. 油箱足够大。

油箱足够大的意思就是，油箱无限。
莫名想起了P5662 [CSP-J2019] 纪念品。
在纪念品一题中，因为可以无限交易，所以可以看做每一天都把所有的卖掉，然后再按需求买进。
而在本题中，因为油箱无限，所以可以看作当我在第 i 个站点时，我可以购买到 1\sim i 所有站点的油。显然，会选择在 1\sim i 所有站点中最便宜的站点买油。

每当我们找到了一个新的最便宜的站点，那么肯定不会在其前面的站点买油，就这新站点最便宜。
那什么时候我们会更换买油的地方呢？当前站点成为新的最便宜的站点时，之后我们会选择在当前站点买油。

因此，我们只需要不断找到更便宜的站点，并在找到的最便宜的站点买油即可。每找到一个更便宜的站点，结算一次，要从上一个最便宜站点买够油开到当前最便宜的站点。

我们可以通过前缀和来快速求出任意两站点间的路程。

注意

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
    int x,id;
};
int n,d;
ll v[100003];
int a;
ll w;
ll tt;
ll ans;

node lst;//记录最便宜的站点

int main(){
    scanf("%d%d",&n,&d);
    for(int i=2;i<=n;i++){
        scanf("%lld",&v[i]);
        v[i]+=v[i-1];//求前缀和
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        if(i==1){//肯定在第一个站点要买油。
            lst.x=a;
            lst.id=i;
        }
        else if(a<lst.x){
            tt=(v[i]-v[lst.id]-w+d-1)/d;//从上一个最便宜的站点到当前最便宜的站点要多少油（向上取整）
            w+=tt*d-(v[i]-v[lst.id]);//还余下多少路程没花完
            ans+=tt*lst.x;//结算花费
            lst.x=a;
            lst.id=i;
        }
    }
    ans+=(v[n]-v[lst.id]-w+d-1)/d*lst.x;//最后在终点还要结算一次
    printf("%lld",ans);
    return 0;
}