美团笔试

前言

我在考完去健身房练腿的时候组间休看到万诺coding已经发了整个的代码和题目，我这里就直接copy题目了（终于不用自己去背题了！）然后这里是原文链接，需要自取美团笔试，今年最难（0329春招实习笔试真题解析）

第一题 小美的生物钟

小美工作得很累，现在已经是深夜，她的生物钟已经乱了！

为了身体健康，她决定现在开始调整自己的生物钟。

现在给定 n 天小美的工作时间，她认为作息是规律的当且仅当每天的工作时间不能超过 k。

可是由于工作需要，她每天需要工作 a_i。

为了身体健康，她决定在工作总时长不变的情况调休，即某天的工作量可以在另外一天完成。

现在她想知道能不能完成调休使得作息是规律的，请你帮她计算一下。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数 T(1 < T < 1000),代表数据组数,每组测试数据描述如下： 对于每一组测试数据:

第一行两个整数 n，k(1 < n < 10^5，1< k< 24)，表示工作天数和作息规律的时长限制。

第二行 n 个整数，第 i 个数为 a_i(1< a_i< 24)，表示工作时长。 数据保证单个测试文件中 Σ n< 10^5。

输出描述

共 T 行，每行一个字符串，若能完成调休使得作息是规律的，输出 “YES”,否则输出 “NO”。

示例 1

输入

2
1 2
2
1 2
3

输出

YES
NO

思路

首先分析题目，我们要判断的是我们的整个工作天数 * 作息时间是否能和我们的工作时长进行比较，当比较后工作时长小于计算所得就可以得到结果。

但是！这里必须要注意，尤其是用ai补全的，我自己用Pycharm就出现这个问题，他补全的是Yes 和 No ，而题目要求是 YES 和 NO。我在写的时候还寻思这题这么简单我咋还能不通过，看了自测的输出才发现这里有问题，所以切记切记先自测再提交。

代码

def can_adjust_schedule(n, k, work_hours):
    total_work_hours = sum(work_hours)
    return total_work_hours <= n * k
T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    work_hours = list(map(int, input().split()))
    if can_adjust_schedule(n, k, work_hours):
        print("YES")
    else:
        print("NO")

第二题 数组2.0

小美有一个长度为 n 的数组 a_1,a_2,…,a_n。

现在每次可以执行以下操作之一： 1.删除当前数组的第一个元素 2.删除当前数组的最后一个元素

若想要数组中极差最小，求最少操作次数。

【极差】数组的极差定义为数组中最大值和最小值的差。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数 T(1< T< 1000),代表数据组数,每组测试数据描述如下： 对于每一组测试数据: 第一行一个整数 n(1< n < 10^5)。

第二行 n 个整数，第 i 个数为 a_i(1< a_i< 10^9) 数据保证单个测试文件中 Σ n <= 10^5。

输出描述

T 行，每行一个整数，表示花费的最少代价。

示例 1

输入

2
2
1 1
2
1 2

输出

0
1

思路

这题我看很多人说自己要么通过50%，要么是自测过提交不通过。

由于每个单元素子数组都满足极差为0，单操作次数为n - 1。显然如果能找到连续显得更的区间，就能减少次数，越长越好。且删除智能从两边进行也就是双端操作。

其中一个思路（虽然我没用，因为实在不想写左右指针）就是左右指针去做，但说实话这个思路写完整个代码会非常冗余。然后我们

然后回到前文，我们的双端操作相当于选取一个连续区间$[i, j]$，操作数为 $(i - 1) + (n - j) = n - (j - i + 1)$。因此我们只需要再数组中找到连续相同的数字的最长区间，答案就是n - （最长区间长度）。

看到这里相信反应过来这题的误区在哪里了，本质上我们还是去找区间而非去找操作数。这个误区我感觉就是很多人没搞定的元凶。

代码

import sys
input_data = sys.stdin.read().split()
if not input_data:
    sys.exit(0)
t = int(input_data[0])
index = 1
results = []
for _ in range(t):
    n = int(input_data[index])
    index += 1
    arr = list(map(int, input_data[index:index+n]))
    index += n
    max_len = 1
    current = 1
    for i in range(1, n):
        if arr[i] == arr[i-1]:
            current += 1
        else:
            if current > max_len:
                max_len = current
            current = 1
    if current > max_len:
        max_len = current
    results.append(str(n - max_len))
sys.stdout.write('\n'.join(results))

第三题 简单打印问题

小美在纸上画了 n 个封闭图形，编号为 1,2,…,n ，第 i 个图形由 m_i 个点描述。他正在捣鼓他的激光打印机打印出这些图形。 这个打印机可以在平面上连续的移动打印，依靠激光发射器实现。激光发射器初始可以位于平面上的任意一个点 S_0 ，随后，由你确定打印顺序，按以下步骤依次打印这 n 个图形：

• 记当前打印的图形编号为 i ；
• 将激光发射器以 x 个单位长度每秒的速度移动到 m_i 点中的其中一个（任选），作为起始端点 S_i ；
• 将激光发射器以 y_i 个单位长度每秒的速度任意的在纸上移动，直到经过全部 m_i 个点后回到起始端点 S_i ；
• 打印过程中不能暂停；若经过非当前图形的点，忽略不计；
• 特别的，如果全部图像打印完毕，则将激光发射器以 x 个单位长度每秒的速度移动到起始选择的点 S_0 ，完成打印。

直接输出整个打印过程需要的最少时间。特别的，如果图形存在重叠，你需要重复打印重叠的部分。

输入描述

第一行输入两个整数 n,x （3<=n<=7; 1<=x<=1000）代表图形数量、不打印时激光发射器的移动速度。 第二行输入 n 个整数 y_1,y_2,…,y_n ( 1<= y_i <= 1000 ) 代表激光发射器打印第 i 个图形的移动速度。 此后，对于第 i 个封闭图形，描述如下： 第一行输入一个整数 m_i ( 3 <= m_i <= 7 ) 代表构成该图形的点的数量。 此后 m_i 行，每行输入两个整数 a,b ( -1000 <= a,b <= 1000 ) 代表点 (a,b) 。保证同一个图形中没有重复的点。

输出描述

输出一个实数，代表最少时间。由于实数的计算存在误差，当误差的量级不超过 10^-6 时，您的答案都将被接受。具体来说，设您的答案为 a ，标准答案为 b ，当且仅当 |a-b| / (max(1,|b|))<10^-6 时，您的答案将被接受。

示例 1

输入

3 1
1 2 1
3
-3 3
0 0
-3 -2
3
1 3
3 0
1 -3
4
-2 1
4 3
5 -2
-3 -5

输出

54.507981260725

说明

在这一样例中，以点 C 作为起点 S_0 ，依次打印图形一、三、二。具体路径描述如下：

首先打印图形一（ C➡️A➡️B➡️C ），耗时。

随后打印图形三（），耗时。

最后打印图形二（ !），耗时。

别忘了加上图形与图形间的移动时间，这一部分耗时。

说明

这题我是真做了一个小时愣是没做出来，万诺coding已经有完整的代码和思路了我这边就不写了，链接在本文最前面。

然后我也会把我自己的代码写在下面，我也才刚从健身房回来，还没去复盘，后续复盘结束我也会把我这个代码哪些地方有问题和哪些地方需要改一并上传。

代码

import sys
import math
import itertools
from functools import lru_cache

def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
def tsp_min_path(points):
    min_dist = float('inf')
    for perm in itertools.permutations(points):
        dist = sum(distance(perm[i], perm[i+1]) for i in range(len(perm)-1))
        dist += distance(perm[-1], perm[0])
        min_dist = min(min_dist, dist)
    return min_dist
def solve():
    n, x = map(int, sys.stdin.readline().split())
    y = list(map(int, sys.stdin.readline().split()))
    shapes = []
    for _ in range(n):
        m = int(sys.stdin.readline().strip())
        points = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
        shapes.append(points)
        print(f"Shape {len(shapes)}: {points}")
    shape_times = []
    for i, shape in enumerate(shapes):
        min_path_length = tsp_min_path(shape)
        shape_times.append(min_path_length / y[i])
    min_travel_time = float('inf')
    dist_between_shapes = [[float('inf') * n for _ in range(n)]]
    for i in range(n):
        for j in range(n):
            if i != j:
                dist_between_shapes[i][j] = min(distance(a, b) for a in shapes[i] for b in shapes[j])
    @lru_cache(None)
    def dp(visited, last):
        if visited == (1 << n) - 1:
            return 0
        min_cost = float('inf')
        for next_shape in range(n):
            if (visited >> next_shape) & 1 == 0:
                cost = dist_between_shapes[last][next_shape] / x + dp(visited | (1 << next_shape), next_shape)
                min_cost = min(min_cost, cost)
        return min_cost
    for start in range(n):
        min_travel_time = min(min_travel_time, dp(1 << start, start))
    total_time = sum(shape_times) + min_travel_time
    print(f"{total_time:.6f}")
solve()