牛客网——牛牛的数组匹配

2022-11-26 216

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 牛客网——牛牛的数组匹配

前言：

不知不觉连续更了21天，（为书包而奋斗），和大家一起学习了21天，虽然有时候太忙就水文章，但是还是学到了很多，认识了很多小伙伴，真的很开心~

今天咱一起学习一下牛牛的数组匹配哈。

一、牛牛的数组匹配

题目：

牛牛的数组匹配_牛客题霸_牛客网

描述

牛牛刚学会数组不久，他拿到两个数组 a 和 b，询问 b 的哪一段连续子数组之和与数组 a 之和最接近。

如果有多个子数组之和同样接近，输出起始点最靠左的数组。

输入描述：

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

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

输出描述：

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

二、解题过程

#include<stdio.h>
/*思路：从完整数组开始，不断去掉前面的一个元素，用剩下的子数组进行下轮比较;
*每轮判断规则(如果满足减去数组2当前的最后一个元素后，如果和数组1差值变小了，
*就继续减去尾元素，直到满足差值最小,得到本轮最优解; 用该值和下一轮进行比较，
*如果下一轮差值更小，则继续切割数组，找更下一轮，直到不满足，然后根据i，j位置输出数组元素;
*/
#include <stdio.h>
int num(int a,int b)
{
  if(a>=b)
  return a-b;
  else
  return b-a;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int a[100]={0};
    int b[100]={0};
    int sum1=0,sum2=0,min,k,l;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d",&b[i]);
    }
  for(int i=0;i<n;i++)
  {
    sum1+=a[i];
  }
  min=sum1;
  for(int i=0;i<m;i++)
  {
    sum2=b[i];
    for(int j=i+1;j<=m;j++)
    {
      if(num(sum1,sum2)<min)
      {
        min=num(sum1,sum2);
        k=i;
        l=j;
      }
      sum2+=b[j];
    }
  }
  for(int i=k;i<l;i++)
  {
    printf("%d ",b[i]);
  }
    return 0;
}