自动搬运

查看原文

来自洛谷，原作者为

	SzTC **

搬运于2025-08-24 21:38:13，当前版本为作者最后更新于2020-10-22 19:16:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

推荐本蒟蒻的博客

附下AC代码，代码的解释都写在注释里了

#include<bits/stdc++.h>			//懒人专用头文件 
using namespace std;
int n,m,cnt;
int a[111][111],b[111][111];	//为了防止损坏a数组，判断的操作应在b数组内执行 
bool f(int r,int c)				//判断长为r，宽为c的锤子是否能够刚好砸完地鼠 
{
	if(cnt%(r*c))return false;	//可行性剪枝：如果地鼠的数量不能被一次砸的地鼠数量整除，那么最后一定不能刚好砸完 
	else
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				b[i][j]=a[i][j];//复制a数组至b数组
			}
		}	
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)//枚举所有的点，一个一个砸下去 
			{	
				if(b[i][j])		//如果b[i][j]不为空，那么就将范围内的地鼠数量全都减去它,实现以i，j为左上角砸b[i][j]次锤子 
				{
					int x=b[i][j];
					for(int k=1;k<=r;k++)
					{
						for(int l=1;l<=c;l++)//枚举锤子的范围，将范围内的地鼠都减去b[i][j] 
						{
							if(i+k-1>n || j+l-1>m)return false;	//如果锤子的范围超出了n*m，那么返回假 
							b[i+k-1][j+l-1]-=x;	 				//减去b[i][j] 
							if(b[i+k-1][j+l-1]<0)return false;	//如果锤子将一个位置的地鼠数量砸成了负数，那么也返回假 
						}
					}
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(b[i][j])
				{
					return false;			//在所有位置的地鼠都砸了一遍过后，如果还有位置有地鼠留下，那么同样返回假
				}
			}
		}
		return true;						//最后，返回真 
	}
}		
int main()
{
	cin>>n>>m;								//输入n与m 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];					//输入每个位置的地鼠数量 
			cnt+=a[i][j];					//统计地鼠一共的数量 
		}
	}	
	int ans=INT_MAX;						//将ans初始化为一个很大的数 
	for(int i=1;i<=n;i++)					//枚举锤子的长 
	{
		for(int j=1;j<=m;j++)				//枚举锤子的宽 
		{
			if(f(i,j))						//判断长为i，宽为j的锤子是否能够刚好砸完地鼠 
			{
				ans=min(ans,(cnt)/(i*j));	//需要砸的次数等于地鼠一共的数量除以一次砸的地鼠数量，最后取最小值 
			}
		}
	}
	cout<<ans;								//最后输出答案 
	return 0;
}

蒟蒻第一次提交题解，欢迎在评论区提出建议！