23届春招 美团java开发4.22笔试凉经

5道算法题，考试平台用的赛码网，考试时长2h，可以用本地IDE。鼠人ac2题，2题通过率0.27，1题通过率0.18，应该寄了。

第一题：小美想要奖学金，小美总共修习了 n 门课程，每门课程都有一个学分 ai ，而这门课小美的成绩是 bi 。小美所在的学校对于奖学金的评定非常简单：只要所有课程的均分不低于一个给定的标准 X，而且没有任何课程挂科，就可以申请奖学金。均分是指所有课程的成绩按照学分加权的平均值，而一门课挂科即该课成绩低于60分。现在小美会给你总共若干次询问，询问在每种课业情况下她能否申请奖学金。用暴力解法ac了。

第二题：小美投骰子，小美需要制作一个骰子。与一般的六面骰子不同，小美需要的骰子总共有 n 面，而且每一面的数字也不同于一般的，这n面的数字需要分别是a1,a2,......an 。当然，骰子是一个正n面体，而且唯一合法的要求是所有相对的两面之和都需要相等，比如一个数字分别为 1,2,3,4,2,3 的六面骰子，那么上面1，下面4，前面2，后面3，左边2，右边3就是合法的方案。因为方案可以很多，所以小美并不在乎究竟是怎么做出这样一个骰子，小美只想知道是否能做出一个合法的骰子。当然，保证n为偶数。也用暴力解法ac了。

第三题：小美在种田。这个游戏的目的是赚尽可能多的钱，游戏中有 n 种作物，其中第 i 种作物从种植到作物成熟采摘需要 ti 天时间，种子买入价格为ai ，作物卖出价格为 bi（一个种子只会产出一个作物，种子可以重复购买）。而游戏内总时间为 m 天，作物的种子种植和采摘、卖出等不耗时间，成熟之前作物没有价值。假设小美只有一块土地（即每个时间只能有一个作物在生长），初始的钱足够多，小美想知道她最多能赚多少钱。感觉像是动态规划问题，没啥思路，通过率18%。

第四题：删除01串。小美给你一个长度为 n 的01串（仅包含字符0和1的串），你可以删除这个串的一个前缀和一个后缀（可以为空），即保留一个原串的连续子串，操作之后整个串的代价为下面两部分之和：1. 被删除的字符1的个数；2. 剩下的子串的字符0的个数。你需要最小化操作的代价，并将其输出。没思路，通过率27%。

第五题：小美打比赛。小美正在参加一个比赛。这个比赛总共有 2k 个人参加（包括小美），编号为1,2,...,2k，开始的时候所有人都在同一个小组。比试的规程如下：假设当前小组有 n 个人（n 为偶数），那么编号大小前 n/2 人分为一个新的小组，后 n/2 人分为一个新的小组，然后两个小组内部分别比试，决出各自的胜者，然后两个小组的胜者进行比试，胜者作为当前小组的优胜者，直到决出最初的小组的优胜者。当然一个人的小组优胜者肯定是他自己。例如如果当前小组有 4 个人，编号为1,2,3,4，那么就会将 1,2 分为一组，3,4分为一组分别比试，然后 1,2 中的胜者和 3,4 中的胜者再进行比试，决出整个小组的胜者。由于每个人的能力各不相同，小美预测了所有人两两比试时的胜者，现在小美想知道预测最终的胜者是谁。做到第五题时就剩10min，也没思路，通过率27%。