蓝桥-2109统计子矩阵
目录
蓝桥 2109统计子矩阵
问题描述
给定一个N×M 的矩阵 A, 请你统计有多少个子矩阵 (最小 1×1, 最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K ?
输入格式
第一行包含三个整数 N,M 和 K.
之后 NN 行每行包含 M 个整数, 代表矩阵 A.
输出格式
一个整数代表答案。
样例输入
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12样例输出
19样例说明
满足条件的子矩阵一共有 19 , 包含:
大小为 1×11×1 的有 10 个。
大小为 1×21×2 的有 3 个。
大小为 1×31×3 的有 2 个。
大小为 1×41×4 的有 1 个。
大小为 2×12×1 的有 3 个。
评测用例规模与约定
对于 30% 的数据, N,M≤20.
对于 70% 的数据, N,M≤100.
对于 100% 的数据, 1≤N,M≤500; 0≤Aij≤1000; 1≤K≤250000000
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
#include <iostream>
using namespace std;
const int N = 510;
int a[N][N];
int n, m, k;
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &a[i][j]);
a[i][j] += a[i - 1][j]; //求第j列前i行的前缀和
}
}
long long ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
//双指针维护左右边界
for (int l = 1, r = 1, sum = 0; r <= m; r++)
{
sum += a[j][r] - a[i - 1][r]; //第l~r列 i~j行的和
//a[j][r] 表示第 r 列的前 j 行的前缀和
//a[j][r]-a[i-1][r] 就是第 r 列从第 i 行到第 j 行的和。
while (sum > k)
{ //如果大于k，左边界右移
sum -= a[j][l] - a[i - 1][l];
l++;
}
ans += r - l + 1;
}
}
}
cout << ans << endl;
}