自动搬运

查看原文

来自洛谷，原作者为

	zumgze 这个家伙很懒，什么都留下

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

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

以下是正文

算法 前缀和+枚举

题意要求最小修改操作次数，可以转化为找一个面积为m的矩形，令其中值为0格子的数目最少

由于我们只知道面积为m，不知道长和宽，所以首先要枚举长宽；然后长宽确定后，再枚举矩形的位置，统计答案

每次统计答案，如果暴力枚举，复杂度将高达$O(m)$。

若我们对每行每列预处理出前缀和，则统计答案的复杂度变为$O(min(length,width))$，预处理复杂度$O(n^2)$

#include<bits/stdc++.h>
using namespace std;
int a[200][200];
int b[200][200];
int main()
{
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x][y]=1;//表示当前格子不为0
		b[x][y]=1;
	}
	for(int i=1;i<=n;i++)//预处理前缀和
		for(int j=1;j<=n;j++)
		{
			a[i][j]+=a[i][j-1];
			b[i][j]+=b[i-1][j];
		}
			
	int ans=m;
	for(int chang=1;chang<=m;chang++)//枚举长宽
	{
		if(m%chang)continue;
		int kuan=m/chang;
		for(int i=1;i+chang-1<=n;i++)//枚举左上角位置
			for(int j=1;j+kuan-1<=n;j++)
			{
				int cnt=m;//用总数减去不为0的格子数
				if(chang>kuan)//统计答案
					for(int jj=j;jj<=j+kuan-1;jj++)
						cnt-=b[i+chang-1][jj]-b[i-1][jj];
				else
					for(int ii=i;ii<=i+chang-1;ii++)
						cnt-=a[ii][j+kuan-1]-a[ii][j-1];
				ans=min(ans,cnt);
			}
	}
	cout<<ans;
	return 0;
}