首先对于这道题一维和二维的前缀和都可以解,那我们此处讲一下一维+双指针和普通没有优化的暴力二维,有兴趣的同学可以去尝试用二维前缀+二分法求一下这个题
第一种解法:暴力二维前缀和(只能拿80分)
因为我们用的暴力解,所以想法很简单把每个位置的前缀和都求出来然后一层一层的for循环就可以了,我们打个表看一下,就明白了,用一下题目给的数据
| arr[i][j] | j=1 | 2 | 3 | 4 |
| i=1 | 1 | 2 | 3 | 4 |
| 2 | 5 | 6 | 7 | 8 |
| 3 | 9 | 10 | 11 | 12 |
然后我们对每个位置进行二维前缀和的计算;我们看一下代码实现
kul[i][j]=kul[i-1][j]+kul[i][j-1]+arr[i][j]-kul[i-1][j-1]; //arr是输入的数据,ful是我们用来记录二维前缀和的数组
| kul[i][j] | j=1 | 2 | 3 | 4 |
| i=1 | 1 | 3 | 6 | 10 |
| 2 | 6 | 14 | 24 | 36 |
| 3 | 15 | 33 | 54 | 78 |
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)
当然了我们用一维前缀和也是可以做出来的,我们的一维是对于列的一维,看一下表格:
| kul[i][j] | j=1 | 2 | 3 | 4 |
| i=1 | 1 | 2 | 3 | 4 |
| 2 | 6 | 8 | 10 | 12 |
| 3 | 15 | 18 | 21 | 24 |
我们的做法是按行从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;
}0.0分
54 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复