CodeM美团点评编程大赛音乐研究

最新推荐文章于 2021-09-12 23:16:40 发布

OFShare

最新推荐文章于 2021-09-12 23:16:40 发布

阅读量868

点赞数

分类专栏： ACM-暴力枚举

本文链接：https://blog.csdn.net/Cui_csdn/article/details/73302440

版权

ACM-暴力枚举专栏收录该内容

5 篇文章

订阅专栏

本文介绍了一个寻找两段音频间最相近部分的算法。通过计算连续子序列的差异值，找到与第一段音频最为接近的匹配项。输入包括两段音频的长度及音高序列，输出则是最小差异值。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 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的最小值

输入例子:

输出例子:

//思路：注意是连续的子序列，直接暴力就行，依次枚举第二个序列的起点，O(n*m)

AC源码：

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int MAXN=1000+10;
vector<int> A,B;
int main()
{
    int tmp;
    int n;
    cin>>n;
    int t1=n;
    while(t1--)
    {
        cin>>tmp;
        A.push_back(tmp);
    }
    int m;
    cin>>m;
    int t2=m;
    while(t2--)
    {
        cin>>tmp;
        B.push_back(tmp);
    }
    int MIN_NUM=(1<<30);
    for(int i=0;i<=m-n;++i)
    {
        int sum=0;
        for(int j=0;j<n;++j)
        {
            sum+=(A[j]-B[i+j])*(A[j]-B[i+j]);
        }
        MIN_NUM=min(MIN_NUM,sum);
    }
    cout<<MIN_NUM<<endl;
    return 0;
}