题解 P6469 【[COCI2008-2009#6] NERED】

· · 题解

算法 前缀和+枚举

题意要求最小修改操作次数，可以转化为找一个面积为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;
}