美团资格赛题解：1-2

由于下学期要参加学校的推研考试，需要考算法题，又正好看到美团举办了一个算法竞赛，抱着练手的态度参加了这次比赛，虽然肯定没办法与众多ACM大神相比，但好在对我来说成绩无所谓了，能对下学期的推研机考有帮助就好。

资格赛总共有六道题，前两道题很简单，3、4、5、6对我来说比较难一些，所以这篇博客就先介绍1，2题吧，剩下的题目会在后面的博客中讨论。

这几道题的题解我都放在了我的github上面，有什么问题请务必联系我。

• 题目1
  • 题目描述
  • 输入描述:
  • 输出描述:
  • 输入例子:
  • 输出例子:
  • 思路:
• 题目2
  • 题目描述
  • 输入描述:
  • 输出描述:
  • 输入例子:
  • 输出例子:
  • 思路

题目1

时间限制：2秒
空间限制：32768K

题目描述

美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。 具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 difference 最小。两段等长音频的 difference 定义为：$difference = \sum_{i=1}^n(a[i] - b[i])^2$，其中 n 表示序列长度，a[i], b[i]分别表示两段音频的音高。现在袋鼠先生想要知道，difference的最小值是多少？数据保证第一段音频的长度小于等于第二段音频的长度。

输入描述:

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

输出描述:

输出difference的最小值

输入例子:

2
1 2
4
3 1 2 4

输出例子:

0

思路:

由于n和m都小于1000，因此最简单的暴力枚举也不用担心超时：直接遍历第二段音频的起点然后记录下遍历过程中difference的最小值即可，代码见github。

题目2

时间限制：1秒
空间限制：32768K

题目描述

组委会正在为美团点评CodeM大赛的决赛设计新赛制。 比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 组的人分别厮杀。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。 现在请问，参赛者小美最多可以活到第几轮（初始为第0轮）？

输入描述:

第一行一个整数 n (1≤n≤ 2^20)，表示参加比赛的总人数。
接下来 n 个数字（数字范围：-1000000…1000000），表示每个参赛者的积分。
小美是第一个参赛者。

输出描述:

小美最多参赛的轮次。

输入例子:

4
4 1 2 3

输出例子:

2

思路

在输入过程中记录下积分小于等于小美积分的人数m，输出$\lfloor log_2(m+1) \rfloor$的值即可，输出代码如下，全部代码见https://github.com/b-liu14/algoritm-solutions/blob/master/nowcoder/championship.cpp。最后的1e-5是为了避免浮点数误差而加上去的。

cout << int(floor(log2(m+1)+1e-5)) << endl;