[已解决]用函数怎么写

牵风

C语言二维数组a[M][N], 给定四个整数LX,LY,RX,RY, 定义函数f(LX,LY,RX,RY)求数组若干元素之和：

输入
输入第一行是两个整数M和N， 表示二维数组a的大小， 0<M,N<=300。
随后有M行， 每行有N个整数，是数组a的数组元素值，值位于-1000到1000之间。
第M+2行是一个整数Q，表示有Q个查询
再随后有Q行，每行有四个空格分开的整数LX,LY,RX,RY。其中0<=LX<=RX<M, 0<=LY<=RY<N


60%的数据， M,N<=20, Q<=20
40%的数据， Q=100000

输出
总共输出Q行
对于每一行查询，输出f(LX,LY,RX,RY)的值。

样例输入 Copy
3 2
-1 -2
-3 -4
-5 -6
3
0 0 0 1
1 1 2 1
1 0 2 1
样例输出 Copy
-3
-10
-18
#include <stdio.h>

int main() {
        int m,n;
        scanf("%d %d",&m,&n);
        int a[m][n];
        for(int i=0; i<m; i++)
                for(int j=0; j<n; j++)
                        scanf("%d",&a[i][j]);
        int lx,ly,rx,ry;
        int q;
        scanf("%d",&q);
        for(int i=0;i<q; i++) {
                int s=0;
                scanf("%d %d %d %d",&lx,&ly,&rx,&ry);
                for(int k=lx; k<=rx; k++)
                        for(int j=ly; j<=ry; j++)
                                s+=a[k][j];

                printf("%d\n",s);
        }
}

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2021-12-1 22:15:57

牵风 发表于 2021-12-1 21:57
为什么会时间超限

表示我的代码不是最优，40% 数据采用 Q = 100000 肯定超时了，时间复杂度：大于 O(n^2)

跳转到最佳答案楼层

傻眼貓咪

1. #include <stdio.h>
   
2. 
   
3. int f(int a, int x, int b, int y, int m, int n, int arr[m][n]){
   
4.     int res = 0;
   
5.     for(size_t i = a; i <= b; i++)
   
6.     for(size_t j = x; j <= y; j++)
   
7.     res += arr[i][j];
   
8.     return res;
   
9. }
   
10. 
    
11. int main()
    
12. {
    
13.     int M, N, Q;
    
14.     scanf("%d%d", &M, &N);
    
15.     int a[M][N];
    
16.     for(size_t m = 0; m < M; m++)
    
17.     for(size_t n = 0; n < N; n++)
    
18.     scanf("%d", &a[m][n]);
    
19.     scanf("%d", &Q);
    
20.     int res[Q], LX, LY, RX, RY;
    
21.     for(size_t q = 0; q < Q; q++){
    
22.         scanf("%d%d%d%d", &LX, &LY, &RX, &RY);
    
23.         res[q] = f(LX, LY, RX, RY, M, N, a);
    
24.     }
    
25.     for(size_t i = 0; i < Q; i++) printf("%d\n", res[i]);
    
26.     return 0;
    
27. }

复制代码

牵风

傻眼貓咪 发表于 2021-12-1 21:51

为什么会时间超限

傻眼貓咪

牵风 发表于 2021-12-1 21:57
为什么会时间超限

表示我的代码不是最优，40% 数据采用 Q = 100000 肯定超时了，时间复杂度：大于 O(n^2)

牵风

傻眼貓咪 发表于 2021-12-1 22:15
表示我的代码不是最优，40% 数据采用 Q = 100000 肯定超时了，时间复杂度：大于 O(n^2)

哦哦