题解 | #最小面积子矩阵#

题目问题

找和>=K,包含元素最少的矩阵

思路

方法一

枚举左上角和右下角，O(n^4)

方法二（优化）

由于所有数值都是非负数，可以枚举上边界和下边界，然后确定上下边界之后枚举左右边界ij即可 要求包含元素最少的子矩阵（右边界固定的时候，左边界往右总和变小，面积也变小） j：最靠右且总和大于等于K的下标的位置

i往右走的时候，j也一定单调往右走，所以可以用双指针优化 O(n^3): 枚举上边界、下边界、一整行

在遍历行的时候，i往右走加的是一列，为了方便快速求出一列的值，可以用前缀和：S(i,j)表示第j列前i个数的和

代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 110,INF=1e8;
int n,m,k;
int s[N][N];

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            cin>>s[i][j];
            s[i][j]+=s[i-1][j];
        }
    int res = INF;
    //枚举上下边界xy
    for(int x=1;x<=n;++x)
        for(int y=x;y<=n;++y){
            //枚举左右边界ij
            for(int i=1,j=1,sum=0;i<=m;++i){
                sum += s[y][i]-s[x-1][i];
                while(sum-(s[y][j]-s[x-1][j])>=k){
                    sum -= s[y][j]-s[x-1][j];
                    j++;
                }
                if(sum>=k) res=min(res,(y-x+1)*(i-j+1));
            }
        }
    if(res==INF) cout<<-1<<endl;
    else cout<<res<<endl;
    return 0;
}