- 要求 矩阵块的和 ,因此要先想到二维前缀和的概念,将矩阵存储起来
- 要想确定一个矩阵,其有上下左右边界,如果全部枚举一定会超时,因此采用 枚举上下边界 ,然后二维问题就转为了一维问题
- 对左右边界进行判定,此时采用 双指针 / 滑块思想 ,枚举右边界,可知左边界r为某值时,此矩阵快可能 >= k,当到达某值时,这里面的矩阵块的和全都是 < 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 ];
}
}