自动搬运

查看原文

来自洛谷，原作者为

	JoeZYQ 不搞颓了||千磨万击，难阻凌云之志；我意已决，定上世人之巅。

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

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

以下是正文

先看题

题目思路

我们设 $vis_i$ 表示第 $i$ 个抽屉有没有放置物品，以此来判断能放置下第 $i$ 个物品的抽屉 $a_i$ 和 $b_i$ 是否为空。

如果这个物品的一个抽屉 $a_i$ 已经放置了另一个物品，就占据这个物品的另一个抽屉 $b_i$，然后抽屉 $b_i$ 中如果原本有物品，那就查询这个物品的 $a_i$ 与 $b_i$ 抽屉，直到找到一个抽屉为空时，并查集便可以优化这一过程。

如果都没有抽屉可以存放物品，就只能将这个物品丢弃。

如果还没看懂，以下是代码的具体实现

#include<iostream>
using namespace std;
int n,l;
const int N=3e5+5;
int vis[N],fa[N];
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void un(int x,int y){
	x=find(x),y=find(y);
	if(x!=y)
		fa[y]=x;
}//并查集基本操作 
int main(){
	cin>>n>>l;
	for(int i=1;i<=l;i++)fa[i]=i;//初始化 
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		if(vis[find(x)]==0||vis[find(y)]==0) {//放得下 
			cout<<"LADICA\n";
			if(vis[find(x)]==0){//可以执行条件1/3 
				vis[find(x)]=1;//标记 
				un(y,x);
			}
			else{//可以执行条件2/4 
				vis[find(y)]=1;//标记 
				un(x,y);
			}
		} 
		else cout<<"SMECE\n";//放不下 
	}
	return 0; 
}