大厂真题 / 美团
美团 4.18 笔试真题 - 研发岗
本场考试概述
考试时间：2026年4月18日 考试岗位：研发岗 难度评级：中等偏难
考点分析：
- 第一题：排序 + 模拟（难度简单）
- 第二题：排序 + 二分查找（难度中等）
- 第三题：贪心 + 树状数组（难度困难）
建议策略：
- 第一题排序标记删除即可，注意处理值相同时优先删左边的规则，快速拿满分
- 第二题对每个点预排距离后二分，注意用距离平方避免浮点误差
- 第三题是经典的”字典序最大 LCS”问题，核心是将两个排列的 LCS 转化为 LIS，再用 BIT + 贪心逐位确定答案
第一题：清除残留数据
题目描述
给定一个长度为 n 的序列，需要删除其中最小的 m 个元素。如果有多个元素值相同，优先删除最左边的。删除后，输出剩余元素按原始顺序排列的结果。
多组测试数据，第一行输入 T。每组数据第一行给出 n 和 m，第二行给出数组 a。保证所有测试数据的 n 之和不超过 200000。
样例
输入
3
5 2
3 1 4 1 5
3 0
1 2 3
5 4
5 4 3 2 1
输出
3 4 5
1 2 3
5
思路分析
第一步：理解删除规则
我们需要从序列中找出最小的 m 个元素并删除它们。关键约束是：当多个元素值相同时，优先删除位于左边的那个。这就要求我们在排序比较时，同值的元素按下标从小到大排，这样取前 m 个就自然满足”优先删左边”的规则。
第二步：确定哪些位置被删除
将所有元素按 (值, 下标) 排序，取排序后的前 m 个元素，记录它们的下标为”被删除”。
第三步：按原顺序输出剩余元素
遍历原数组，跳过被标记为删除的位置，将剩余元素按顺序输出。
以样例第一组为例：数组 [3, 1, 4, 1, 5]，m=2。按 (值, 下标) 排序后为 (1,1), (1,3), (3,0), (4,2), (5,4)。取前 2 个：下标 1 和 3 被删除。原数组中保留下标 0, 2, 4 对应的 3, 4, 5。
题解代码
import sys
input = sys.stdin.readline
def solve():
n, m = map(int, input().split())
a = list(map(int, input().split()))
if m == 0:
print(*a)
return
# 按 (值, 下标) 排序，取前 m 个的下标标记为删除
indices = sorted(range(n), key=lambda i: (a[i], i))
removed = set(indices[:m])
# 按原顺序输出未被删除的元素
res = [a[i] for i in range(n) if i not in removed]
print(*res)
T = int(input())
for _ in range(T):
solve()
复杂度分析
时间复杂度：O(n log n)，排序为主要开销。 空间复杂度：O(n)，存储排序后的下标和删除集合。
第二题：二维坐标系
题目描述
平面上有 n 个点。对于每对点 (i, j)（i != j），定义 c[i][j] 为：以点 i 为圆心、dist(i, j) 为半径的圆内（含圆上）的其他点的数量（不包括 i 和 j 本身）。即 c[i][j] 等于满足 k != i 且 k != j 且 dist(i, k) <= dist(i, j) 的点 k 的数量。定义 c[i][i] = 0。
多组测试数据，第一行输入 T。每组数据第一行给出 n，接下来 n 行每行两个整数表示坐标。保证所有测试数据的 n 之和不超过 5000。
样例
输入
1
4
0 0
1 0
0 1
1 1
输出
0 1 1 2
1 0 2 1
1 2 0 1
2 1 1 0
思路分析
第一步：理解 c[i][j] 的含义
c[i][j] 本质上是：以点 i 为圆心画一个刚好经过点 j 的圆，这个圆内部和边界上还有多少个其他点（不算 i 和 j）。
直觉上，如果 j 离 i 很远，那圆就很大，里面包含的其他点就多。
第二步：为什么排序 + 二分？
对于固定的点 i，c[i][j] 只依赖于 dist(i, j) 的相对大小。如果我们预先将所有其他点按到 i 的距离排好序，那么对于任意 j，只需要知道”距离 <= dist(i, j) 的点有多少个”，这正好是排序后的前缀计数问题，可以用二分查找 O(log n) 解决。
具体地：对于点 i，计算它到其余所有点的距离平方（用 int64 避免浮点），排序后对每个 j 二分查找 upper_bound(dist_sq(i, j))，得到”距离 <= dist(i, j) 的点个数”，再减 1（排除 j 本身）。
第三步：为什么用距离平方？
坐标范围到 10^6，距离平方最大约 (2 * 10^6)^2 = 4 * 10^12，在 int64 范围内。使用距离平方可以完全避免浮点运算和精度问题，且不影响大小比较。
第四步：算法流程
- 对每个点 i，计算到其余 n-1 个点的距离平方，存入列表并排序
- 对每对 (i, j)，用 bisect_right 在 i 的排序列表中查找 dist_sq(i, j) 的上界位置，该位置就是”距离 <= dist(i, j)”的点数（不含 i），减去 1（排除 j）就是 c[i][j]
以样例为例：4 个点构成单位正方形。对于点 0=(0,0)：到点 1 距离平方=1，到点 2 距离平方=1，到点 3 距离平方=2。排序后为 [1, 1, 2]。c[0][1]：bisect_right([1,1,2], 1) = 2，减 1 = 1。c[0][3]：bisect_right([1,1,2], 2) = 3，减 1 = 2。
题解代码
import sys
from bisect import bisect_right
input = sys.stdin.readline
def solve():
n = int(input())
pts = []
for _ in range(n):
x, y = map(int, input().split())
pts.append((x, y))
# 对每个点 i，预计算到其他所有点的距离平方并排序
dist_sorted = [[] for _ in range(n)]
for i in range(n):
dists = []
xi, yi = pts[i]
for j in range(n):
if j == i:
continue
dx = pts[j][0] - xi
dy = pts[j][1] - yi
dists.append(dx * dx + dy * dy)
dists.sort()
dist_sorted[i] = dists
# 计算 c[i][j]
out = []
for i in range(n):
row = []
xi, yi = pts[i]
for j in range(n):
if j == i:
row.append(0)
else:
dx = pts[j][0] - xi
dy = pts[j][1] - yi
d2 = dx * dx + dy * dy
# 在排序列表中找 <= d2 的个数，减 1 排除 j
cnt = bisect_right(dist_sorted[i], d2) - 1
row.append(cnt)
out.append(" ".join(map(str, row)))
print("\n".join(out))
T = int(input())
for _ in range(T):
solve()
复杂度分析
时间复杂度：O(n^2 log n)，对每个点排序 O(n log n)，共 n 个点；查询共 n^2 次，每次 O(log n)。 空间复杂度：O(n^2)，存储每个点的距离排序数组。
第三题：最长公共子序列3
题目描述
给定两个长度为 n 的排列 p 和 q（即 1 到 n 的全排列），求它们的字典序最大的最长公共子序列（LCS）。输出 LCS 的长度和具体序列。
多组测试数据，第一行输入 T。每组数据第一行给出 n，接下来两行分别给出排列 p 和 q。保证所有测试数据的 n 之和不超过 200000。
样例
输入
3
4
1 3 2 4
3 4 1 2
5
1 2 3 4 5
5 4 3 2 1
9
9 2 6 7 3 8 1 4 5
6 2 7 9 4 8 3 5 1
输出
2
3 4
1
5
4
6 7 8 5
思路分析
第一步：LCS 转化为 LIS
两个排列的 LCS 有一个经典转化：构造序列 c，其中 c[i] 表示 p[i] 在 q 中出现的位置（即 q 的逆排列在 p[i] 处的值）。那么 p 和 q 的 LCS 等价于 c 的最长递增子序列（LIS）。
为什么？p 和 q 的公共子序列要求选出的元素在 p 中下标递增，同时在 q 中下标也递增。如果我们用 c[i] = pos_q(p[i])（p[i] 在 q 中的位置），那么选择一组下标 i1 < i2 < … < ik 使得 c[i1] < c[i2] < … < c[ik]，就恰好对应 p 和 q 的一个公共子序列。因此 LCS 长度 = LIS(c) 的长度。
第二步：求字典序最大的 LIS
现在问题变成：在序列 c 上找字典序最大的 LIS。这里”字典序最大”是指 LIS 对应的原始值（p[i] 的值）字典序最大，而不是 c 值字典序最大。
关键思路：贪心地从左到右逐位确定结果。对于结果的第 k 位，我们想选最大的 p[i] 值，同时满足：
- c[i] 严格大于已选的上一个 c 值（保证递增性）
- 从位置 i 开始（含 i），剩余的后缀中能形成的 LIS 长度足够填满剩余位数
条件 2 需要预计算：对每个位置 i，从 i 开始的”后缀 LIS 长度”（即以 c[i] 为起点、只考虑 i 及之后的元素能形成的最长递增子序列长度）。
第三步：用 BIT 计算后缀 LIS 长度
从右到左扫描，维护一个树状数组（BIT），BIT 的下标对应 c 值，存储的是以 >= 该 c 值开头的 LIS 最大长度。
对于位置 i，suffix_lis[i] = 1 + BIT 查询 (c[i]+1, n) 的最大值（即在 i 之后、c 值严格大于 c[i] 的位置中最长递增子序列长度的最大值）。然后将 suffix_lis[i] 更新到 BIT 的位置 c[i]。
由于 BIT 通常用于前缀查询，而我们需要后缀最大值查询（查 [c[i]+1, n] 的最大值），可以做坐标翻转：令 c’[i] = n + 1 - c[i]，则查询 [c[i]+1, n] 变成查询前缀 [1, c’[i]-1] 的最大值，标准 BIT 即可处理。
第四步：贪心选择——按 p[i] 值从大到小扫描
LIS 的总长度 L = max(suffix_lis[i])。我们需要逐步选出 L 个元素。
贪心策略：
- 将所有位置按 p[i] 值从大到小排序（值相同不可能，因为是排列）
- 维护 last_c = -1（上一个选中元素的 c 值）和 remain = L（还需选多少个）
- 按 p 值从大到小遍历候选位置 i，检查是否满足：
- c[i] > last_c（递增约束）
- suffix_lis[i] >= remain（后缀够长）
- 满足则选中 i，更新 last_c = c[i]，remain -= 1
- 但还需注意位置约束：选中 i 后，后续只能选位置 > i 的元素
第五步：处理位置约束的细节
上述贪心有一个微妙之处：选中位置 i 后，后续候选必须在 i 之后（位置更大）。但我们按 p 值降序排列候选，位置是乱序的。
更精确的做法：
- 按 p[i] 值降序排列所有位置
- 对于结果的每一位，从当前候选中找第一个满足 c[i] > last_c、位置 > last_pos 且 suffix_lis[i] >= remain 的位置
- 但直接暴力扫描可能退化为 O(n^2)
优化方法：对候选按 p 值降序排列后，维护 last_pos（上一个选中位置）。对于每一轮选择，扫描候选列表，跳过位置 <= last_pos 或 c[i] <= last_c 的，找到第一个满足 suffix_lis[i] >= remain 的。由于每个位置最多被扫描和跳过一次（一旦被跳过或选中就不再考虑），总复杂度仍为 O(n log n)。
以样例第三组为例：p = [9,2,6,7,3,8,1,4,5]，q = [6,2,7,9,4,8,3,5,1]。构造 c：p[0]=9 在 q 中位置 4，p[1]=2 在 q 中位置 2，p[2]=6 在 q 中位置 1，p[3]=7 在 q 中位置 3，p[4]=3 在 q 中位置 7，p[5]=8 在 q 中位置 6，p[6]=1 在 q 中位置 9，p[7]=4 在 q 中位置 5，p[8]=5 在 q 中位置 8。c = [4,2,1,3,7,6,9,5,8]。LIS(c) 长度为 4（如子序列 1,3,6,8 或 1,3,5,8 等）。字典序最大的对应原值为 6,7,8,5。
题解代码
import sys
input = sys.stdin.readline
def solve():
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
# pos_in_q[v] = v 在 q 中的位置（0-indexed）
pos_in_q = [0] * (n + 1)
for i in range(n):
pos_in_q[q[i]] = i
# c[i] = p[i] 在 q 中的位置
c = [pos_in_q[p[i]] for i in range(n)]
# 用 BIT 求后缀 LIS 长度
# suffix_lis[i] = 以 c[i] 开头、只考虑位置 >= i 的最长递增子序列长度
# BIT 维护前缀最大值（坐标翻转后）
bit = [0] * (n + 2)
def query(pos):
"""查询 [1, pos] 的最大值"""
res = 0
while pos > 0:
res = max(res, bit[pos])
pos -= pos & (-pos)
return res
def update(pos, val):
"""更新位置 pos 的值（取 max）"""
while pos <= n:
bit[pos] = max(bit[pos], val)
pos += pos & (-pos)
suffix_lis = [0] * n
# 从右到左扫描，坐标翻转：c'[i] = n - c[i]
# 查询 c[i]+1..n-1 的最大值 = 查询翻转后 1..n-1-c[i] 的前缀最大值
for i in range(n - 1, -1, -1):
# 翻转坐标：原始 c[i] 在 [0, n-1]，翻转为 n - c[i]（范围 [1, n]）
flipped = n - c[i] # [1, n]
# 查询原始坐标 > c[i] 即翻转坐标 < flipped，即前缀 [1, flipped-1]
best = query(flipped - 1) if flipped > 1 else 0
suffix_lis[i] = best + 1
# 更新翻转坐标 flipped 位置
update(flipped, suffix_lis[i])
total_lis = max(suffix_lis)
# 贪心选取字典序最大的 LIS
# 按 p[i] 值降序排列所有位置
order = sorted(range(n), key=lambda i: -p[i])
result = []
last_c = -1
last_pos = -1
remain = total_lis
ptr = 0 # 指向 order 中的当前位置
while remain > 0:
for idx in range(ptr, n):
i = order[idx]
# 位置必须在 last_pos 之后，c 值必须大于 last_c
if i <= last_pos or c[i] <= last_c:
continue
if suffix_lis[i] >= remain:
result.append(p[i])
last_c = c[i]
last_pos = i
remain -= 1
ptr = idx + 1
break
print(total_lis)
print(*result)
T = int(input())
for _ in range(T):
solve()
复杂度分析
时间复杂度：O(n log n)。BIT 更新和查询各 O(log n)，共 n 次；排序 O(n log n)；贪心选取过程中每个位置最多被访问一次（指针 ptr 单调前进），总计 O(n)。 空间复杂度：O(n)，存储 c 数组、suffix_lis 数组、BIT 和排序数组。
小结
- 第一题是排序模拟题，核心是按 (值, 下标) 排序来处理”同值优先删左边”的规则，标记删除后按原顺序输出，是一道送分题
- 第二题利用”距离平方”避免浮点，对每个点预排距离后二分查找，本质是将”圆内点计数”转化为”有序数组前缀计数”，是排序 + 二分的经典应用
- 第三题是本场最难的题目，将两个排列的 LCS 转化为 LIS 是关键的第一步转化，随后用 BIT 计算后缀 LIS 长度，再用贪心按值降序逐位确定答案，需要对 LIS 的结构有深入理解