AcWing 4405. 统计子矩阵(双指针+前缀和)
原题链接
中等
作者:
逸误
,
2024-03-13 23:40:55
,
所有人可见
,
阅读 16
//由于具有单调性,r往右走的时候l要么不动要么也单调往右走,就可以双指针了
//双指针将O(n^2)直接优化到O(n)
//双指针总是:for更新快指针,里面嵌套while更新慢指针(公式)
//思路:遍历i和j,固定下来,作为矩阵上下界(O(N^2)),用双指针遍历左右界,O(n)
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 505;
int n,m,k;
int s[N][N];//这里不需要二维前缀和,这个是每一列的一位前缀和,第一个元素是列号
LL res;
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&s[i][j]);
s[i][j]+=s[i-1][j];//预处理好这个一维前缀和
}
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++)//双指针
{
//根据双指针,l应随着运行过程判断慢慢右移
sum+=s[j][r]-s[i-1][r];//快指针移动了一格,更新sum
while(sum>k)//sum过大,需要更新慢指针了
{
sum-=s[j][l]-s[i-1][l];
l++;
}
//i和j是固定的,需要枚举的
//现在得到了对于这个r来说能接受的最小l
res+=r-l+1;
}
cout<<res<<endl;
return 0;
}