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

「牛客网C」初学者入门训练BC156

news 2025/7/25 20:16:26

🐶博主主页：@ᰔᩚ. 一怀明月ꦿ

❤️‍🔥专栏系列：线性代数，C初学者入门训练

🔥座右铭：“不要等到什么都没有了，才下定决心去做”

🚀🚀🚀大家觉不错的话，就恳求大家点点关注，点点小爱心，指点指点🚀🚀🚀

题目：BC156 牛牛的数组匹配

描述：

牛牛刚学会数组不久，他拿到两个数组 a 和 b，询问 b 的哪一段连续子数组之和与数组 a 之和最接近。如果有多个子数组之和同样接近，输出起始点最靠左的数组。

输入描述：

第一行输入两个正整数 n 和 m ，表示数组 a 和 b 的长度。

第二第三行输入 n 个和 m 个正整数，表示数组中 a 和 b 的值。

输出描述：

输出子数组之和最接近 a 的子数组

示例1

输入：
2 6
30 39 
15 29 42 1 44 1
输出：
29 42
示例2

输入：
6 1
50 47 24 19 46 47 
2
输出：
2
解题思路：询问 b 的哪一段连续子数组之和与数组 a 之和最接近，我们可以先计算每一个b数组元素b[i]与数组 a 之和sum的差值绝对值，然后记录差值，和此时的坐标，然后分别计算b[i]+b[i+1]，b[i]+b[i+1]+b[i+2],b[i]+b[i+1]+b[i+2]+...+b[m]和sum的差值绝对值，然后分别记录差值，和此时的坐标。最后按照起始和末尾坐标打印。

解题详细过程：
#include<stdio.h>
int Abs(int sum1,int sum2)
{if(sum1>sum2)return sum1-sum2;return sum2-sum1;
}
void Fun(int sum1,int b[],int m)//Fun这个函数就是完成“询问 b 的哪一段连续子数组之和与数组 a 之和最接近”这个功能。
{int i=0,j=0,S=0,E=0;//S就是记录起始的位置，E记录末尾的位置int sum2=0;int min=sum1;//min记录sum2和sum1的差值绝对值，但是初始化为a数组之和for(i=0;i<m;i++){sum2=b[i];for(j=i+1;j<=m;j++){if(Abs(sum1,sum2)<min){min=Abs(sum1,sum2);S=i;E=j;}sum2+=b[j];}}for(i=S;i<E;i++)//打印{printf("%d ",b[i]);}printf("\n");
}
int main()
{printf("请输入a数组的长度,b数组的长度\n");int n=0,m=0;scanf("%d %d",&n,&m);int a[n];int b[m];printf("请输入a数组\n");int i=0;int sum=0;//统计b数组的和for(i=0;i<n;i++){scanf("%d",&a[i]);sum+=a[i];}printf("请输入b数组\n");for(i=0;i<m;i++){scanf("%d",&b[i]);}Fun(sum,b,m);return 0;
}
关于这个Abs函数我想重点叙述一下
int Abs(int sum1,int sum2)
{if(sum1>sum2)return sum1-sum2;return sum2-sum1;
Abs就是absolute value（绝对值）缩写，这里计算两个数的差值的绝对值，但注意,因为有人就会想我直接把这两个数定义为无符号整形，再以无符号整形打印，不一样可以得到绝对值吗，如果这样想就错了，无符号整形型的数的二进制是没有符号位的，所以原码，反码，补码，转换是有所差异的，例如-1无符号数是一个很大的数，而不是1