蓝桥杯真题 2109.统计子矩阵

原题地址:1.统计子矩阵 - 蓝桥云课

问题描述

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

输入格式

第一行包含三个整数 N,MN,M 和 KK.

之后 NN 行每行包含 MM 个整数, 代表矩阵 AA.

输出格式

一个整数代表答案。

具体代码和思路如下:

#include <iostream>
using namespace std;

int n,m,k;
int a[501][501];
long long ans = 0;

int main()
{
    cin>>n>>m>>k;
    for (int i = 1;i <= n;++i){
        for (int j = 1;j <= m;++j){
            cin>>a[i][j];
            //将每一行都看成一个整数，来进行前缀和的操作
            a[i][j] += a[i - 1][j];
        }
    }
    for (int i = 1;i <= n;++i){//滑动窗口的上边界
        for (int ii = i;ii <= n;++ii){//滑动窗口的下边界
            int l = 1,r = 1;//l为滑动窗口的左边界，r为滑动窗口的右边界
        int sum = 0;//sum为当前滑动窗口内所有元素的和,即小区间[l,r]的和
            for (r = 1;r <= m;++r){//更新右边界
                sum += a[ii][r] - a[i - 1][r];//加入新扩大的窗口的边界值
                while (sum > k){//当sum大于k时，就停止更新右边界r，开始让左边界l向右移，直到区间[l,r]内的值小于等于k
                    sum -= a[ii][l] - a[i - 1][l];//由于左边界l要向右移，所以要减去原来左边界上的值
                    l++;
                }
                //当区间[l,r]内的所有元素和小于等于k时，就说明该区间内的所有子区间的区间和都要小于等于k
                ans += r - l + 1;
            }
        }
    }
    cout<<ans;
    return 0;
}