首页 > 试题广场 >

音乐研究

[编程题]音乐研究

热度指数：532 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 difference 最小。两段等长音频的 difference 定义为：
difference = SUM((a[i] - b[i])² )(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

输入

输出

算法知识视频讲解

shyyhs

发表于 2020-08-17 22:22:47

直接暴力n^2即可,好吧,还是少写这种题.. #include <bits/stdc++.h> using namespace std; const int N=1005; int a[N],b[N]; int main() { int n,m; scanf("%d", 展开全文

llvYeriji

发表于 2021-12-26 10:05:26

本题用暴力枚举，每次将b数组（第二段音频）里的m段（m为第一段音频的长度）与第一段音频比较，将最小的difference找出来即可。 ">int main() { int m,n,k; int a[1010],b[1010]; int min=1e9,dif; sca 展开全文

可爱抱抱呀😥

发表于 2022-03-03 11:59:02

//运行时间160ms占用内存17964KB import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); 展开全文

little-greenhand

发表于 2023-08-09 10:52:44

思路：直接暴力枚举，遍历第二个数组中每个子列与第一个数组的difference，不过交的时候遇到一个问题，没有通过全部样例，通过多组自测用例尝试，发现数据小时没错，猜测是difference初始值的问题（一开始给difference开的1000，只过了5%，开了100000，过了25%），所以在遍历展开全文

Mo1e

发表于 2023-04-01 13:55:20

类似滑动窗口，将a[n]从左侧开始与b[m]进行n个数的比较并计算出difference，暂存于temp中，随后使用min函数选出最小的difference。 #include <bits/stdc++.h> using namespace std; int main(){ i 展开全文

威风镰鼬

发表于 2022-01-24 23:11:21

思路暴力枚举，O(nm) 注意要等长，所以母串最多到n-m 代码 #pragma GCC optimize("Ofast", "inline", "-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits 展开全文

天谎

发表于 2019-12-16 21:05:40

链接：https://ac.nowcoder.com/acm/problem/13222来源：牛客网题目描述美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。具体地说，就是在第二段音频中找到一展开全文

地主家的傻孩子

发表于 2020-04-12 21:19:02

import java.util.Scanner; //音乐研究--滑动窗口 public class Main { private int helper(int[] num1, int[] num2) { int sum = Integer.MAX_VALUE; 展开全文

Acmer_W

发表于 2020-04-08 20:06:59

虽然这题很简单，但还是想写一次题解（来自小菜鸡的辛酸，终于会写一道题了.....）这道题思路很简单，就是暴力枚举。。。。。直接上代码#include <cstdio>#include <iostream>#include <algorithm>using na 展开全文

问题信息

C++工程师 golang工程师 2017 iOS工程师安卓工程师枚举运维工程师前端工程师算法工程师测试工程师 PHP工程师 c#工程师美团测试开发工程师大数据开发工程师 Java工程师

来自：CodeM 2017美...

难度：

8条回答 10收藏 3956浏览

通过挑战的用户

牛客79759...

2022-08-26 12:06:33
pein531

2022-01-10 20:46:33
彭1996

2021-08-07 13:29:19
牛客11688...

2020-11-01 08:33:55
牛客66043...

2020-08-20 12:34:51

音乐研究

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题