当前位置：首页 > article >正文

58区间和+44开发商购买土地（前缀和）

article 2025/3/3 20:39:05

58. 区间和（第九期模拟笔试）

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。

输出描述

输出每个指定区间内元素的总和。

输入示例

输出示例

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 个正整数。

输出描述

请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

输入示例

输出示例

提示信息

如果将区域按照如下方式划分：

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;
}

查看全文

http://www.kler.cn/a/567069.html