自动搬运

查看原文

来自洛谷，原作者为

	louhao088 这个家伙不懒，但还是什么都没留下

搬运于2025-08-24 21:49:11，当前版本为作者最后更新于2021-08-26 10:55:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道贪心好题。

首先我们发现如果在他周围比他低的点有抽水机，那么他肯定不用再放抽水机了。

很自然的得到一个想法，就是把所有点按高度排序。依次判断要抽水的点四周能连出去的点中是否有抽水机。

这个操作可以用并查集维护，把高的点放入四周低的点的并查集中，每次查询他所在并查集有没有抽水机，没有就加上。

可以证明这样操作能使答案最优。

时间复杂度 $O( nm \log{nm})$ 。

代码如下

#include<bits/stdc++.h>
using namespace std;
//static char buf[1000000],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define re register
const int maxn=1e3+5;
inline int read()
{
	char ch=getchar();bool f=0;int x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
void print(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,m,a[maxn][maxn],f[maxn][maxn],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},fa[maxn*maxn],s[maxn*maxn],ans=0;
struct node
{
	int x,y,num;
}b[1000005];
bool cmp(node a,node b){return a.num<b.num;}
int getf(int x){if(fa[x]==x)return x;fa[x]=getf(fa[x]);return fa[x];}
void gett(int x,int y)
{
	x=getf(x),y=getf(y);if(x==y)return ;
	fa[x]=y;s[y]|=s[x];
}
int id(int x,int y){return (x-1)*m+y;}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),m=read();memset(a,0x3f,sizeof a);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			a[i][j]=read();
			if(a[i][j]<0)a[i][j]=abs(a[i][j]);
			else f[i][j]=1;
			b[id(i,j)]=(node){i,j,a[i][j]};
			fa[id(i,j)]=id(i,j);
		}
	sort(b+1,b+id(n,m)+1,cmp);

	for(int i=1;i<=n*m;i++)
	{
		for(int j=0;j<4;j++)
		{
			int tx=b[i].x+dx[j],ty=b[i].y+dy[j];
			if(a[tx][ty]<=b[i].num)gett(id(tx,ty),id(b[i].x,b[i].y));
		}
		if(b[i].num!=b[i+1].num)
		{
			for(int j=i;;j--)
			{
				if(b[j].num!=b[i].num)break;
				if(f[b[j].x][b[j].y])
				{
					int h=getf(id(b[j].x,b[j].y));
					if(!s[h])s[h]=1,ans++;
				}
			}
		}
	}
	cout<<ans;
 	return 0;
}

如有帮到你，请点赞支持，谢谢。