题解：P11320 [NOISG 2020 Qualification] Fuel Station

· · 题解

思维难度：绿。

代码难度：绿。

感觉难度：上位绿。建议评绿。

首先我们对于 X_i 排序。

我们假设初始燃油为 0，我们需要维护到达一个加油站时（未加油）的车辆的燃油情况（因此允许负数）。

因为车辆的燃油情况的数组是不允许负数的，所以这个数组中的最小值的相反数就是需要的初始燃油的量。

因为如果初始燃油为最小值的相反数，整个数组都会加上最小值的相反数，所以这个数组的最小值就会变成 0，就符合题意了。

讨厌的是，每个加油站有个限制 B_i，它限制了当初始燃油过高的时候，某些加油站不能使用。

因此我们考虑对于 B_i 排序，当 B_i 变大的时候，会出现某些加油站不能使用的情况。

我们可以考虑枚举所有加油站可能存在的情况，并计算相应的 F 的取值范围。（设此时的枚举到的加油站的限制为 B，则初始油量 F \leq B 即可），如果需要的初始燃油的量符合以上的取值范围，输出即可（因为我们要最小值）。如果不符合，说明需要删除更多的加油站。删除一个加油站 i 对于燃油的代价是这个加油站往后的所有的燃油情况都会减去 A_i。

为了代码方便，我们可以将终点也视为一个加油站。

因此这个数组需要满足后缀加法，全局查询最小值，线段树走起！

因为每个加油站只会删除一次，因此时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=3e5+5;
ll n,d;
struct p{
    ll x,a,b,id;
}sta[maxn];
bool cmp1(p a,p b){
    return a.x<b.x;
}
bool cmp2(p a,p b){
    return a.b<b.b;
}
//线段树 
ll fir[maxn],num[maxn<<2],add[maxn<<2];
void pushup(ll rt){
    num[rt]=min(num[rt<<1],num[rt<<1|1]);
}
void pushdown(ll rt){
    if(add[rt]){
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        num[rt<<1]+=add[rt];
        num[rt<<1|1]+=add[rt];
        add[rt]=0;
    }
}
void build(ll l,ll r,ll rt){
    if(l==r){
        num[rt]=fir[l];
        return;
    }
    ll m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
} 
void update(ll L,ll R,ll l,ll r,ll c,ll rt){
    if(R<L)return;
    if(L<=l && r<=R){
        num[rt]+=c;
        add[rt]+=c;
        return;
    }
    ll m=(l+r)>>1;
    pushdown(rt);
    if(L<=m)update(L,R,l,m,c,rt<<1);
    if(m<R)update(L,R,m+1,r,c,rt<<1|1);
    pushup(rt);
}
void init(){
    ll sy=0;//计算初始油为0的油箱情况 
    for(int i=1;i<=n;i++){
        sy-=sta[i].x-sta[i-1].x;
        fir[i]=sy;
        sy+=sta[i].a;
        sta[i].id=i;
    }
}
int main(){
    scanf("%lld%lld",&n,&d);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&sta[i].x,&sta[i].a,&sta[i].b);
    }
    sta[++n]={d,0,2000000005,n};//第n+1个加油站表示终点
    sort(sta+1,sta+n+1,cmp1);//按照x排序 
    init();
    build(1,n,1);
    sort(sta+1,sta+n+1,cmp2);//按照b排序 
    ll F;
    for(int i=1;i<=n;i++){
        F=sta[i].b;
        if(-num[1]<=F){//需要补油的量小于初始油量 
            printf("%lld\n",-num[1]);
            break;
        }
        while(1){
            update(sta[i].id+1,n,1,n,-sta[i].a,1);
            //当一个加油站不能使用的时候，这个加油站以后的汽车油量都会减去sta[i].a
            if(sta[i+1].b==F)i++;
            else break;
        } 
    }
    return 0;
}