58. 區間和（第九期模擬筆試）

題目描述

給定一個整數數組 Array，請計算該數組在每個指定區間內元素的總和。

輸入描述

第一行輸入為整數數組 Array 的長度 n，接下來 n 行，每行一個整數，表示數組的元素。隨后的輸入為需要計算總和的區間下標：a，b （b > = a），直至文件結束。

輸出描述

輸出每個指定區間內元素的總和。

輸入示例

5
1
2
3
4
5
0 1
1 3

輸出示例

3
9

提示信息

數據范圍：
0 < n <= 100000

malloc和free函數頭文件為<stdlib.h>,直接利用一個數組a即可。

#include<stdio.h>
#include<stdlib.h>
#define N 100005
int main(){int num;scanf("%d",&num);int *a=(int *)malloc(sizeof(int)*(num+1));int t;for(int i=0;i<num;i++){scanf("%d",&t);if(i==0)a[i]=t;else a[i]=a[i-1]+t;}int m,n;while(scanf("%d%d",&m,&n)!=EOF){printf("%d\n",a[n]-a[m-1]);}free(a);return 0;
}

44??開發商購買土地（第五期模擬筆試）

題目描述

在一個城市區域內，被劃分成了n * m個連續的區塊，每個區塊都擁有不同的權值，代表著其土地價值。目前，有兩家開發公司，A 公司和 B 公司，希望購買這個城市區域的土地。?

現在，需要將這個城市區域的所有區塊分配給 A 公司和 B 公司。

然而，由于城市規劃的限制，只允許將區域按橫向或縱向劃分成兩個子區域，而且每個子區域都必須包含一個或多個區塊。 為了確保公平競爭，你需要找到一種分配方式，使得 A 公司和 B 公司各自的子區域內的土地總價值之差最小。?

注意：區塊不可再分。

輸入描述

第一行輸入兩個正整數，代表 n 和 m。?

接下來的 n 行，每行輸出 m 個正整數。

輸出描述

請輸出一個整數，代表兩個子區域內土地總價值之間的最小差距。

輸入示例

3 3
1 2 3
2 1 3
1 2 3

輸出示例

0

提示信息

如果將區域按照如下方式劃分：

1 2 | 3
2 1 | 3
1 2 | 3?

兩個子區域內土地總價值之間的最小差距可以達到 0。

數據范圍：

1 <= n, m <= 100；
n 和 m 不同時為 1。

解題思路：用a，b數組分別記錄每一行和每一列的值后計算前綴和。

按行劃分最小值min1初始值設為a[n-1]，for循環進行劃分，從i行劃分，差值為abs(a[n-1]-2*a[i])。與min1比較大小，決定是否更新min1的值。

按列劃分也是如此。

abs()：定義在<stdlib.h>頭文件中。它用于計算整數的絕對值。
fabs()：這個函數定義在<math.h>頭文件中。它用于計算浮點數的絕對值。

#include<stdio.h>
#include<stdlib.h>
int main(){int n,m;scanf("%d%d",&n,&m);int *a=(int *)malloc(sizeof(int)*n);//按行int *b=(int *)malloc(sizeof(int)*m);//按列int num,i,j;for(i=0;i<n;i++){for(j=0;j<m;j++){scanf("%d",&num);a[i]+=num;b[j]+=num;}}//計算前綴和for(i=1;i<n;i++){a[i]+=a[i-1];}for(j=1;j<m;j++){b[j]+=b[j-1];}//按行和按列劃分的最小值int min1=a[n-1],min2=b[m-1];int t;//當前劃分的差值for(i=0;i<n-1;i++){t=abs(a[n-1]-2*a[i]);if(t<min1)min1=t;}for(i=0;i<m-1;i++){t=abs(b[m-1]-2*b[i]);if(t<min2)min2=t;}int min=(min1<min2)?min1:min2;printf("%d\n",min);free(a);free(b);return 0;
}