自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

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

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

以下是正文

提供一种全新的可并堆做法，也是我考场上想到的做法（虽然当时没调出来）。

首先，可以倒着考虑整个过程：想象时间倒着流动到零，第 $i$ 个箱子刚开始在 $b_i$，当时间流动到 $t_i$ 时才可以开始移动，当时间回到 $0$ 时，它需要位于 $a_i$。

根据这个想法，可以首先将所有箱子按 $t$ 从大到小排序。至于当 $t$ 相同时如何处理稍后再说。

这样，就会发现，每到达一个新的 $t_i$ 时，就有（至少）一个新的箱子可以移动，而“先前”因为被这个箱子挡住的其它箱子也在此时才可以开始继续往 $a_i$ 的方向移动。

因此可以开一个数组 $mov$，$mov_i$ 表示有几次移动是在（排序后的）$t_i$ 这个时刻“开始后”才可以进行的。不难发现得出这个数组后，具体每次移动的顺序是不重要的，因为总是可以找到一种移动的方法使每一步（如果还需要的话）都可以让一个箱子往“终点”的方向移动。

只要知道了这个数组的值，接下来判断是否有解就简单了：贪心地让每次尽量让每个操作都靠前进行，如果最后到 $0$ 时刻还有操作需要进行则无解，否则有解。

代码片段：

for(int i=1;i<=n;i++){
	int x=mov[i];
	mov[i]=min(mov[i],a[i].t-a[i+1].t);
	x-=mov[i];
	mov[i+1]+=x;
}
if(mov[n+1]){
	cout<<"No\n";
}else{
	cout<<"Yes\n";
}

接下来问题就是怎么搞出 $mov$ 数组了，首先可以想到一个 $n^2$ 暴力跳的方法：

仍然是按照时间从后到前遍历每个箱子（后面的编号都指按时间从大到小排序后的编号）。遍历到第 $i$ 个箱子时，此时它应该仍然处在 $b_i$ 的位置，要前往 $a_i$。为了方便，先假设 $a_i>b_i$。首先对于每个箱子预处理出它后面第一个时间“晚于”它（实际上是 $t$ 比它更小）的箱子的编号。那么就可以找到箱子 $i$ 后面第一个从时间上看可能会挡住它的箱子 $x$，再判断它是否会挡住这个箱子。

• 如果会挡住，那么 $i$ 就还需要等待到 $x$ 号箱子可以移动后才可以继续前进。此时就将 $mov_i$ 增加移到 $x$ 号箱子前的步数，然后假设当前箱子移到了 $x$ 号箱子的位置，并继续考虑当 $x$ 号箱子可以动之后应该怎么继续往前走，再修改 $mov_x$，一直这样往后跳箱子。
• 直到右边的那个箱子 $x$ 不会挡住当前的箱子 $i$，也就是现在 $i$ 可以直接移动到 $a_i$ 了，那么就给 $mov_x$ 增加这次移动需要的步数，并结束循环。

$a_i<b_i$ 的情况也差不多，就是一些操作要反过来。

最坏时间复杂度确实是 $O(n^2)$，当然碰到 B 性质就是 $O(n)$ 的了。

上面说着简单，但是实际上实现也有不少细节。对于 $a_i>b_i$，当 $i$ 要移到箱子 $x$ 前时，它真正到的位置应该是 $b_i-y$，其中 $y$ 是在 $i$ 和 $x$ 之间的箱子的个数。跳的时候用一个变量存储当前往前偏移了几格，最后一次移动时还要加回来。

这种暴力跳的方法不需要考虑当 $t$ 相同时按什么排序，因为实际上不按 $t$ 排序直接做也是一样的。

赛时写的 $60$ 分代码（去除多余注释等），可以参考代码理解前面的内容。

考虑优化。首先注意到许多跳的步骤都是重复计算的，（仍然只考虑 $a_i>b_i$）当一个箱子 $x$ 挡住了左边多个箱子时，左边多个箱子都要分别计算一遍对 $mov_x$ 的贡献。

实际上，可以延迟处理这些内容，或者说，对于每个箱子 $i$ 记录当时间到达 $t_i$ 时所有“排队等待”的箱子要去的位置（具体的箱子的编号都是不重要的，只需要知道 $a$ 的值即可）。当真正轮到这个箱子 $x$ 时，需要做到取出其中所有不会被下一个要“跳”的箱子挡住的位置，并直接计算答案加到 $mov_x$ 中，而剩下会被挡住的箱子则统一计算移动步数（它们这一段的移动步数显然是相同的），并合并到下一个箱子的信息中。

也就是，需要找到一个数据结构，可以取出其中最小的几个数，以及与另一个相同的数据结构合并。

不难想到可并堆。每个箱子都开一个 pb_ds 的 priority_queue，然后按上面所说的做即可。每个 $a_i$ 都只会被压入和取出一次，总共合并次数也是 $<n$ 的，所以总复杂度优化到了 $O(n\log n)$。细节太多，赛时想到这里但是没时间写了。

除了 $60$ 分代码需要考虑的以外，这里还需要考虑当 $t$ 相同时，按什么排序。为了保证不会出现类似箱子“插队等待”的问题，需要保证 $t$ 相同的所有 $a_i<b_i$ 的箱子按 $b_i$（$a_i$）从大到小排序，而所有 $a_i>b_i$ 的箱子按 $b_i$（$a_i$）从小到大排序，这样处理顺序才是正确的。如果 cmp 函数碰到的两个箱子一个 $a_i<b_i$，一个 $a_j>b_j$，也不能随便返回，因为这样可能导致最后排出来还是乱序（经测试会 WA 三个点）。一种方法是把所有 $a_i<b_i$ 的箱子排到 $a_j>b_j$ 的箱子前面。

sort(a+1,a+1+n,[](box aa,box bb){
	if(aa.t!=bb.t)return aa.t>bb.t;
	if((aa.a<aa.b)!=(bb.a<bb.b))return aa.a<aa.b;
	if(aa.a<aa.b)return aa.a>bb.a;
	else return aa.a<bb.a;
});

处理完所有细节后，这道题就可以用可并堆 AC 了。即使我写的常数可能有点大，但是时间最大的测试点也只有 850ms。

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define int long long
using namespace std;
const int N=2e5+5;
struct box{
	int a,b,t,id;
	int l1,r1;
}a[N];
int idt[N];
int mov[N];
__gnu_pbds::priority_queue<int,greater<int>>qmn[N];
__gnu_pbds::priority_queue<int,less<int>>qmx[N];
void mian(){
	int n;cin>>n;
	for(int i=0;i<=n+3;i++)mov[i]=idt[i]=a[i].a=a[i].b=a[i].t=a[i].id=a[i].l1=a[i].r1=0;
	for(int i=1;i<=n;i++)cin>>a[i].a>>a[i].b>>a[i].t,a[i].id=i;
	stack<int>st;
	for(int i=1;i<=n;i++){
		while(!st.empty()&&a[st.top()].t>a[i].t)st.pop();
		if(!st.empty())a[i].l1=st.top();
		st.emplace(i);
	}
	while(!st.empty())st.pop();
	for(int i=n;i>=1;i--){
		while(!st.empty()&&a[st.top()].t>a[i].t)st.pop();
		if(!st.empty())a[i].r1=st.top();
		st.emplace(i);
	}
	sort(a+1,a+1+n,[](box aa,box bb){
		if(aa.t!=bb.t)return aa.t>bb.t;
		if((aa.a<aa.b)!=(bb.a<bb.b))return aa.a<aa.b;
		if(aa.a<aa.b)return aa.a>bb.a;
		else return aa.a<bb.a;
	});
	for(int i=1;i<=n;i++)idt[a[i].id]=i;
	for(int i=1;i<=n;i++){
		qmx[i].clear();qmx[i].push(a[i].a);
		qmn[i].clear();qmn[i].push(a[i].a);
	}
	for(int i=1;i<=n;i++){
		if(a[i].a<a[i].b){
			int x=idt[a[i].l1];
			while(qmx[i].size()&&(!x||qmx[i].top()>=a[x].b+(int)(qmx[x].size()+qmx[i].size())-1)){
				mov[i]+=(a[i].b+qmx[i].size()-1)-qmx[i].top();
				qmx[i].pop();
			}
			if(x)mov[i]+=qmx[i].size()*(a[i].b-(a[x].b+qmx[x].size()));
			qmx[x].join(qmx[i]);
		}else{
			int x=idt[a[i].r1];
			while(qmn[i].size()&&(!x||qmn[i].top()<=a[x].b-(int)(qmn[x].size()+qmn[i].size())+1)){
				mov[i]+=qmn[i].top()-(a[i].b-qmn[i].size()+1);
				qmn[i].pop();
			}
			if(x)mov[i]+=qmn[i].size()*((a[x].b-qmn[x].size())-a[i].b);
			qmn[x].join(qmn[i]);
		}
	}
	for(int i=1;i<=n;i++){
		int x=mov[i];
		mov[i]=min(mov[i],a[i].t-a[i+1].t);
		x-=mov[i];
		mov[i+1]+=x;
	}
	if(mov[n+1]){
		cout<<"No\n";
	}else{
		cout<<"Yes\n";
	}
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int c,t;cin>>c>>t;
	while(t--){
		mian();
	}
	return 0;
}

另外据机房同学所说，这里好像也可以不用堆来存，只需要用另一个数组存下原本上面代码对应的堆的大小就行了。不过感觉这样代码会更复杂，所以我没写。