自动搬运

查看原文

来自洛谷，原作者为

	reinforest ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้ (？

搬运于2025-08-24 23:06:24，当前版本为作者最后更新于2025-02-10 07:24:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思维难度：绿。

代码难度：绿。

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

首先我们对于 $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;
}