「CF627C」 Package Delivery

题意

需要驾驶一辆汽车行驶 \(d\) 单位的距离，汽车的油箱最多装 \(n\) 个单位的油，出发时邮箱装满了油。路上有 \(m\) 个加油站，第 \(i\) 个加油站在距离起点 \(x_i\) 的位置，每个单位的油价值 \(p_i\)。

求到达终点的最小花费，如果无法到达输出 -1。

分析

这题和 CSP-J2023 T2 很像，只加了油箱容量的限制，但大体思路是差不多的。

\(nxt_i\) 表示第 \(i\) 个加油站后第一个比它价格低的站。

因为当前价格较高，所以应尽量到 \(nxt_i\) 再加油，若无法直接到达 \(nxt_i\)，就在 \(i\) 加油，然后跑到 \(i+1\)。

用单调栈预处理 \(nxt_i\)，因为对加油站按 \(x_i\) 排序，总时间复杂度 \(O(m\log m)\)(应该没有 dalao 用桶排)。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
const ll maxn=200005;
ll d,n,m,nxt[maxn],now,sum;
struct node{ll x,p;inline bool operator<(const node&b)const{return x<b.x;}}a[maxn];
stack<ll>st;
signed main(){
    d=read(),n=read(),m=read();
    for(ll i=1;i<=m;++i){
        a[i].x=read(),a[i].p=read();
    }
    sort(a+1,a+m+1);
    a[m+1]=(node){d,-1};
    st.push(m+1);
    for(ll i=m;i>=0;--i){
        while(!st.empty()&&a[st.top()].p>a[i].p)st.pop();
        nxt[i]=st.top(),st.push(i);
    }
    now=n;
    for(ll i=0;i<=m;++i){
        ll num=max(0ll,min(a[nxt[i]].x-a[i].x,n)-now);
        sum+=num*a[i].p,now-=a[i+1].x-a[i].x-num;
        if(now<0)puts("-1"),exit(0);
    }
    printf("%lld",sum);
    return 0;
}