链接：https://ac.nowcoder.com/acm/problem/13222
来源：牛客网
来源：牛客网
美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。
具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 difference 最小。两段等长音频的 difference 定义为：
difference = SUM(a[i] - b[i])2 (1 ≤ i ≤ n),其中SUM()表示求和
其中 n 表示序列长度，a[i], b[i]分别表示两段音频的音高。现在袋鼠先生想要知道，difference的最小值是多少？数据保证第一段音频的长度小于等于第二段音频的长度。
具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 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的最小值
主要注意每次选取从第i个，i的值不能大于其差值
#include<bits/stdc++.h>
using namespace std;const int num = 1000;
int a[num]; //第一段音高
int b[num]; //第二段音高
int main()
{
int n,m; //定义音频长度
//第一段音高存储
cin >> n; //第一段音频长度
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
//第二段音高存储
cin >> m;
for(int i=1;i<=m;i++){
cin >> b[i];
}
long long difference=1000000000;
for(int i=1;i<=m-n+1;i++) //从i个选取，i不能超过m与n的差值
{
long long sum=0;
for(int j=1;j<=n;j++)
{
sum=sum+(b[i+j-1]-a[j])*(b[i+j-1]-a[j]);
}
if(sum<difference)
{
difference=sum;
}
}
cout << difference;
return 0;
}
全部评论
(0) 回帖