一开始没想出双指针到底怎么用
用一维数组也是可以的,速度应该比二维数组快
参考文献
acwhr大佬的题解
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N = 5100;
LL n, m ,k, ans;
LL a[N][N],s[N][N];
int main()
{
scanf("%lld%lld%lld", &n, &m, &k);
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
scanf("%lld", &a[i][j]);
s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];//前缀和预处理
}
}
//运用双指针来枚举矩阵
for(int l = 1; l <= m; l ++)//枚举矩阵的左边
{
for(int r = l; r <= m; r ++)//枚举矩阵的右边
{
for(int i = 1, j = 1; i <=n; i ++)//枚举矩阵的上下边,左右边已有
{
//这里不要将前缀和的公式放在函数中调用 会超时!
while(j <= i && (s[i][r] - s[j - 1][r] - s[i][l - 1] + s[j - 1][l - 1]) > k) j ++;//x1=j,y1=l,x2=i,y2=r;
if(j <= i) ans += (i - j + 1);//有可能最小的矩阵也不符合范围
}
}
}
printf("%lld", ans);
return 0;
}