自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:34:49，当前版本为作者最后更新于2021-10-05 10:38:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

定位签到题，所以不讲部分分（雾

按题意模拟即可。但是直接模拟是 $O(n^4)$ 的，考虑优化。容易想到的优化就是用数据结构维护。发现 $v$ 的值很小，所以只要开 $10$ 个 set 来维护每种棋子就可以了。时间复杂度 $O(n^2\log{n})$。

Code:

#include<set>
#include<cctype>
#include<cstdio>
#define rg register
inline char rc()
{
	static char buf[524288],*pn=buf,*pe=buf;
	return (pn==pe)&&(pe=(pn=buf)+fread(buf,1,524288,stdin),pn==pe)?EOF:*pn++;
}
inline int read()
{
	int x=0;
	char cc=rc();
	while(!isdigit(cc))cc=rc();
	while(isdigit(cc))x=(x*10+cc-'0'),cc=rc();
	return x;
}
using std::set;
int n,m,k,v,r,c;
int a[1003][1003];
int bs[1003][1003];
int res[1003][1003];
struct bd
{
	int x,y;
	bool operator <(const bd &t)const
	{
		if(bs[x][y]==bs[t.x][t.y])
		{
			if(x+y==t.x+t.y)return x<t.x;
			return (x+y)<(t.x+t.y);
		}
		return bs[x][y]>bs[t.x][t.y];
	}
};
inline bd make(int x,int y)
{
	bd nw;
	nw.x=x,nw.y=y;
	return nw;
}
set<bd>S[13];
inline void upd(int r,int c)
{
	int vl=a[r][c];
	bd nw=make(r,c);
	if(!S[vl].count(nw))return;
	S[vl].erase(nw);
	++bs[r][c],S[vl].insert(nw);
}
int main()
{
	n=read(),m=read();k=n*m;
	for(rg int i=1;i<=n;++i)
	{
		for(rg int j=1;j<=m;++j)
		{
			a[i][j]=read();
			bs[i][j]+=(i==1),bs[i][j]+=(i==n);
			bs[i][j]+=(j==1),bs[i][j]+=(j==m);
			S[a[i][j]].insert(make(i,j));
		}
	}
	for(rg int i=1;i<=k;++i)
	{
		v=read();
		set<bd>::iterator tmp=S[v].begin();
		r=tmp->x,c=tmp->y;
		S[v].erase(tmp),res[r][c]=i;
		if(r>1)upd(r-1,c);
		if(r<n)upd(r+1,c);
		if(c>1)upd(r,c-1);
		if(c<m)upd(r,c+1);
	}
	for(rg int i=1;i<=n;++i)
	{
		for(rg int j=1;j<m;++j)printf("%d ",res[i][j]);
		printf("%d\n",res[i][m]);
	}
	return 0;
}