义乌建设局网站打不开,上海集团网站建设,网站维护一次多少钱,搜索引擎国外牛客网 BC156 牛牛的数组匹配
题目描述
描述
牛牛刚学会数组不久#xff0c;他拿到两个数组 a 和 b#xff0c;询问 b 的哪一段连续子数组之和与数组 a 之和最接近。
如果有多个子数组之和同样接近#xff0c;输出起始点最靠左的数组。
输入描述#xff1a;
第一行输…牛客网 BC156 牛牛的数组匹配
题目描述
描述
牛牛刚学会数组不久他拿到两个数组 a 和 b询问 b 的哪一段连续子数组之和与数组 a 之和最接近。
如果有多个子数组之和同样接近输出起始点最靠左的数组。
输入描述
第一行输入两个正整数 n 和 m 表示数组 a 和 b 的长度。
第二第三行输入 n 个和 m 个正整数表示数组中 a 和 b 的值。
输出描述
输出子数组之和最接近 a 的子数组 思路分析
基于滑动窗口的思想从数组最左边开始将连续子数组之和与numaa数组里的总和进行比较。
步骤流程
1.定义所需要输入的数n和m需要输入的数组a和b输入a数组时记得求a数组的和numa
2.输入完成后开始进行循环
3.这里需要考虑一个特殊情况就是当m1时就无须进行比较了直接将b【0】输出即可。
定义left和right分别指向数组最左边的最小连续数组的下标left0right1为了之后的方便输出我们再定义一个cl和cr记录left和right的值。
循环的条件是leftright的同时rightm。
每一次循环求left和right之间值的和sum并将sum与numa的差值与min定义的最小差值最开始等于numa进行比较如果小于min就将该值赋给min同时将left的值赋给clright的值赋给cr之后再判断sum的值是否大于numa大于则left小于则right防止连续子数组越来越大
循环结束后输出cl和cr之间的值。
完整代码
#include stdio.h
#includestdlib.h
int main() {int a[50]{0};int b[50]{0};int n0;int m0;scanf(%d %d,n,m);int suma0;for(int i0;in;i){scanf(%d,a[i]);sumaa[i];}for(int i0;im;i){scanf(%d,b[i]);}int left0;int right1;int cl0;int cr0;int minsuma;//最小差值最开始numaif(m1)//m1的情况直接输出{printf(%d,b[0]);return 0;}while(leftrightrightm){int sum0;for(int ileft;iright;i){sumb[i];}if(abs(sum-suma)min)//abs函数用来求两者之间差的绝对值{minabs(sum-suma);clleft;crright;}if(sumsuma)//判断sum与numa的情况{left;}if(sumsuma){right;}}for(int icl;icr;i)//输出{printf(%d ,b[i]);}return 0;
}
