题目描述

美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。

具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 difference 最小。两段等长音频的 difference 定义为：
difference = SUM(a[i] - b[i])2 (1 ≤ i ≤ n),其中SUM()表示求和
其中 n 表示序列长度，a[i], b[i]分别表示两段音频的音高。现在袋鼠先生想要知道，difference的最小值是多少？数据保证第一段音频的长度小于等于第二段音频的长度。

输入描述:

第一行一个整数n(1 ≤ n ≤ 1000)，表示第一段音频的长度。
第二行n个整数表示第一段音频的音高（0 ≤ 音高 ≤ 1000）。
第三行一个整数m(1 ≤ n ≤ m ≤ 1000)，表示第二段音频的长度。
第四行m个整数表示第二段音频的音高（0 ≤ 音高 ≤ 1000）。

输出描述:

输出difference的最小值

示例1

输入

复制

2
1 2
4
3 1 2 4

输出

复制

0

本题采用暴力枚举的方法，每次将b数组（第二段音频）里的m段（m为第一段音频的长度）与第一段音频比较，将最小的difference找出来即可。

 题面上注意difference的形式和音频长度就可以啦。

AC正解

#include<stdio.h>
int main()
{
    int m,n,k;
    int a[1010],b[1010];
    int min=1e9,dif;//先给min赋最大值
    scanf("%d",&m);
    for(int i=0;i<m;++i)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        scanf("%d",&b[i]);
    }
    for(int i=0;i<n-m+1;++i)//外层循环表示每次从第二段音频的位置取对应第一段音频的数据
    {
        k=0;
        dif=0;
        for(int j=i;j<=i+m-1;++j)//内层循环对相应段数据进行比较
        {
            if(b[j]!=a[k])
                dif+=(b[j]-a[k])*(b[j]-a[k]);//求每轮的difference
                k++;
        }
        if(dif<min)
            min=dif;
    }
    printf("%d",min);
    return 0;
}
//下面一行是我的自测用例
/*
4
5 6 3 4
9
3 4 5 6 3 3 3 3 5
*/