自动搬运

查看原文

来自洛谷，原作者为

	FReQuenter ? ?? ??? ???? ?????

搬运于2025-08-24 22:35:42，当前版本为作者最后更新于2023-08-11 13:50:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现数据很小。所以基本上随便写写都能过/cf

首先预处理出每个人和每个椅子之间的距离。注意用的是欧几里得距离，别用曼哈顿距离算。

然后来考虑每个人选哪个椅子。这里我们发现，让人去选椅子很麻烦（因为要排序距离）所以直接把所有人到椅子的距离都单独拿出来排序依次处理。这样子一个人选了一个椅子之后就不会动了。

最后统计一下每个椅子被选了多少次。如果大于一次就会炸。然后就做完了。

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define sqr(x) ((x)*(x))
using namespace std;
int r,c,cp,cs,ans,cr,sit[25005];
char a[505][505];
pair<int,int> pas[25005],seat[25005],sited[25005];
pair<int,pair<int,int>> ge[25005];
int dis(int x,int y){
	return sqr(pas[x].fi-seat[y].fi)+sqr(pas[x].se-seat[y].se);
}
signed main(){
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>a[i][j];
			if(a[i][j]=='X') pas[++cp]={i,j};
			if(a[i][j]=='L') seat[++cs]={i,j};
		}
	}
	for(int i=1;i<=cp;i++){
		for(int j=1;j<=cs;j++){
			ge[++cr]={dis(i,j),{i,j}};
		}
	}
	sort(ge+1,ge+cr+1);
	for(int i=1;i<=cr;i++){
		if(!sit[ge[i].se.fi]){
			int u=ge[i].se.fi,v=ge[i].se.se;
			if(!sited[v].se) sit[u]=v,sited[v]={u,1};
			else if(dis(u,v)==dis(sited[v].fi,v)) sit[u]=v,sited[v].se++;
		}
	}
	for(int i=1;i<=cs;i++) if(sited[i].se>1) ans++;
	cout<<ans;
}