7-统计子矩阵：二维前缀和 + 双指针

本题链接：7.统计子矩阵 - 蓝桥云课 (lanqiao.cn)

给定一个 N×M 的矩阵 A，请你统计有多少个子矩阵 (最小 1×11×1，最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K?

输入样例：

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

输出样例：

19

思路：

1. 要求 矩阵块的和 ，因此要先想到二维前缀和的概念，将矩阵存储起来
2. 要想确定一个矩阵，其有上下左右边界，如果全部枚举一定会超时，因此采用 枚举上下边界 ，然后二维问题就转为了一维问题
3. 对左右边界进行判定，此时采用 双指针 / 滑块思想 ，枚举右边界，可知左边界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 ];

        }

}

代码：

#include<iostream>
using namespace std;

int n, m, k;
const int N = 510;
int s[N][N];
int res = 0;

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] ;
		}
	}
	long long res = 0;
	//遍历上下边界
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			int l = 1,sum = 0;
			for (int r = 1; r <= m; r++) {
				sum += s[j][r] - s[i - 1][r];
				while (sum > k && l <= m) {
					sum = sum - s[j][l] + s[i - 1][l];
					l++;
				}
				res += r - l + 1;
			}
		}
	}
	cout << res;
	return 0;
}

以上是本文全部内容，如果对你有帮助点个赞再走吧~  ₍˄·͈༝·͈˄*₎◞ ̑̑