首先对于这道题一维和二维的前缀和都可以解,那我们此处讲一下一维+双指针和普通没有优化的暴力二维,有兴趣的同学可以去尝试用二维前缀+二分法求一下这个题

第一种解法:暴力二维前缀和(只能拿80分)

因为我们用的暴力解,所以想法很简单把每个位置的前缀和都求出来然后一层一层的for循环就可以了,我们打个表看一下,就明白了,用一下题目给的数据

然后我们对每个位置进行二维前缀和的计算;我们看一下代码实现

kul[i][j]=kul[i-1][j]+kul[i][j-1]+arr[i][j]-kul[i-1][j-1];    //arr是输入的数据,ful是我们用来记录二维前缀和的数组

kul数组每个位置记录的都是1~i和1~j所以元素的总和,然后我们直接暴力对每个前缀和做差与题目给的k进行比对小的话结果就加1大的话就直接break；

if(kul[k][p]-kul[i-1][p]-kul[k][j-1]+kul[i-1][j-1]<=val)          //如果可以就一直算下去,不行直接break,也算是个小优化吧
{
    flag++;
}else{
    break;
}

我们看一下完整代码(感兴趣的同学可以优化一下二维前缀可以拿满分,这里就分享一下暴力的做法吧)

#include<stdio.h>
#include<string.h>
#define max 505
int arr[max][max],kul[max][max];
int main()
{
	int n,m,k,val,i,j,p;
	scanf("%d%d%d",&n,&m,&val);
	memset(kul,0,sizeof(kul));
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
		{
			scanf("%d",&arr[i][j]);
			kul[i][j]=kul[i-1][j]+kul[i][j-1]+arr[i][j]-kul[i-1][j-1];
		}
	}
	int flag=0,mi=0;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
		{
			for(k=i; k<=n; k++)
			{
				for(p=j; p<=m; p++)
				{
					if(kul[k][p]-kul[i-1][p]-kul[k][j-1]+kul[i-1][j-1]<=val)
					{
						flag++;
					}
					else
					{
						break;
					}
				}
			}
		}
	}
	
	printf("%d",flag);
	return 0;
}

第二种解法:一维前缀和加双指针(满分AC)

当然了我们用一维前缀和也是可以做出来的,我们的一维是对于列的一维,看一下表格:

我们的做法是按行从1开始计算,但我们加的值是按照列来计算的,如果满足题目给的k我们就直接加上就可以了,如果没有满足我们用while循环来进行列的向右遍历，看下源码

#include<stdio.h>
int s[505][505];
int main( )
{
	int n,m,k;
	scanf("%d%d%d",&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];
		}
	}
	long long int res=0;
	for(int i=1; i<=n; i++)
	{
		for(int j=i; j<=n; j++)
		{
			for(int left=1,right=1,sum=0; right<=m; right++)
			{
				sum+=s[j][right]-s[i-1][right];
				while (sum>k)
				{
					sum-=s[j][left]-s[i-1][left];
					left++;
				}
				res+=right-left+1;
			}
		}
	}
	printf("%lld",res);
	return 0;
}