2023暑期实习-笔试-美团-技术综合-算法策略方向

公司：美团

考试题型：编程 4 道、选择 3 道

笔试平台：赛码

时长：120分钟

时间：2023-03-25 19:00-21:00

编程题

火车迷

描述

小美是一个火车迷。最近她在观察家附近火车站的火车驶入和驶出情况，发现火车驶入和驶出的顺序并不一致。经过小美调查发现，原来这个火车站里面有一个类似于栈的结构，如下图所示：

例如可能1号火车驶入了火车站中的休息区s，在驶出之前2号火车驶入了。那么在这种情况下，1号火车需要等待2号火车倒车出去后才能出去（显然被后面驶入的2号火车挡住了，这个休息区s只有一个出入口）。

出于好奇，小美统计了近些天的火车驶入驶出情况，开始统计和结束统计时休息区s中均是空的。由于中途疏忽，小美觉得自己好像弄错了几个驶入驶出顺序，想请你帮她验证一下。值得注意的是，小美虽然可能弄错了顺序，但对火车的记录是不重不漏的。

形式化地来形容休息区s，我们视其为一个容量无限大的空间，假设两列火车 i 和 j 同时处于休息区s中，驶入时刻 T_in满足 T_in(i)<T_in(j)，则驶出时间T_out必定满足T_out(i)>T_out(j)，即，先进后出。

输入描述

第一行一个整数T表示数据组数。

对每组测试而言：

第一行一个整数n，表示观察到的火车数量。

第二行n个整数 x₁,x₂,...,x_n，表示小美记录的火车驶入休息区s的顺序。

第三行n个整数 y₁,y₂,...,y_n，表示小美记录的火车驶出休息区s的顺序。

1≤T≤10,1≤n≤50000,1≤x_i,y_i≤n, 且{x_n} 、{y_n} 均为{1,2,3,...,n}的一个排列，即1~n这n个数在其中不重不漏恰好出现一次。

输出描述

对每组数据输出一行：如果小美记录的驶入和驶出顺序无法被满足则输出No，否则输出Yes。

示例

输入

3

3

1 2 3

1 2 3

3

1 2 3

3 2 1

3

1 2 3

3 1 2

输出

Yes

Yes

No

说明：

对第一组数据：

每辆火车刚驶入便立刻驶出即可满足此记录。

对第二组数据：

[ <- 休息区出口（空初始状态）

[1 <- 休息区出口（1号驶入）

[1 2 <- 休息区出口（2号驶入）

[1 2 3 <- 休息区出口（3号驶入）

[1 2 <- 休息区出口（3号驶出）

[1 <- 休息区出口（2号驶出）

[ <- 休息区出口（1号驶出）

记录可以被此种方案满足。

对第三组数据：

[ <- 休息区出口（空初始状态）

[1 <- 休息区出口（1号驶入）

[1 2 <- 休息区出口（2号驶入）

[1 2 3 <- 休息区出口（3号驶入）

[1 2 <- 休息区出口（3号驶出）

发现1号被2号堵住，无法先于2号驶出。

可以证明，亦不存在其他驶入驶出方案使得第三组数据满足要求。

思路

使用栈这来模拟火车驶入驶出的过程，参考**************************。

代码

T = int(input())
for k in range(T):
    n = int(input())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    stack = []
    j = 0
    for i in x:
        stack.append(i)
        while stack and stack[-1] == y[j]:
            stack.pop()
            j += 1
    if len(stack) == 0:
        print("Yes")
    else:
        print("No")

分糖

描述

小美因乐于助人的突出表现获得了老师的嘉奖。老师允许小美从一堆 n 个编号分别为 1,2,...,n 的糖果中选择任意多个糖果作为奖励（每种编号的糖果各一个），但为了防止小美一次吃太多糖果有害身体健康，老师设定了一个限制：如果选择了编号为 i 的糖果，那么就不能选择编号为 i-1, i-2, i+1, i+2 的四个糖果了。在小美看来，每个糖果都有一个对应的美味值，小美想让她选出的糖果的美味值之和最大！作为小美的好朋友，请你帮帮她！

输入描述

第一行一个整数n，表示糖果数量。

第二行n个整数 a₁,a₂,...,a_n，其中 a_i表示编号为 i 的糖果的美味值。

1≤n≤50000, 1≤a_i≤10000

输出描述

输出一行一个数，表示小美能获得的糖果美味值之和最大值。