大厂真题 / 美团
美团 5.9 笔试真题 - 研发岗
本场考试概述
考试时间：2026年5月9日 考试岗位：研发岗 难度评级：中等偏难
考点分析：
- 第一题：线性扫描（难度简单）
- 第二题：构造（难度中等）
- 第三题：DP + 线段树（难度困难）
建议策略：
- 前两题尽量稳拿，是拉开名次的基本盘
- 第三题先排序 + 朴素 DP 拿到 60-70% 部分分，再考虑用线段树把双下标约束解耦优化到正解
- 数据范围 $n \leq 10^5$，注意写 $O(n \log n)$ 复杂度的解法，避免 $O(n^2)$ TLE
第一题：平稳风段
题目描述
给定长度为 $n$ 的风速序列和阈值 $d$。定义连续段 $[l, r]$ 为”平稳段”，当且仅当对所有相邻位置都有 $\lvert a_i - a_{i-1} \rvert \leq d$。请输出所有平稳段的最大长度。
多组测试数据，保证所有测试数据的 $n$ 之和不超过 $10^5$。
样例
输入
2
5 2
3 4 7 6 7
1 0
100
输出
3
1
思路分析
观察题目性质
题目要求在序列上找最长连续段，使得段内每对相邻元素差的绝对值不超过 $d$。这是一个典型的”最长合法连续子数组”问题。
算法选择
由于判定条件只涉及相邻两个元素的关系，不需要维护窗口内的全局信息（如最大最小值），因此无需滑动窗口或单调队列——一次简单的线性扫描就够了。
实现要点
维护 cur 表示以当前位置为右端点的平稳段长度，best 记录全局最长。每到一个新位置 $i$，如果 $\lvert a_i - a_{i-1} \rvert \leq d$，说明当前段可以延伸，cur += 1；否则段已断开，cur 重置为 1。每步用 cur 刷新 best。
单个元素自成一段，所以答案至少为 1。
题解代码
import sys
input = sys.stdin.readline
def solve():
T = int(input())
out = []
for _ in range(T):
n, d = map(int, input().split())
a = list(map(int, input().split()))
cur = 1
best = 1
for i in range(1, n):
if abs(a[i] - a[i - 1]) <= d:
cur += 1
if cur > best:
best = cur
else:
cur = 1
out.append(str(best))
print("\n".join(out))
solve()
复杂度分析
时间复杂度：$O(n)$，每个元素访问常数次。 空间复杂度：$O(n)$，存放输入数组。
第二题：正整数矩阵
题目描述
给定一个 $n \times m$ 的非负整数矩阵 $A$。每次操作选择两个不同的格子 $(i_1, j_1)$ 与 $(i_2, j_2)$，执行 $A[i_1][j_1] -= 1$ 与 $A[i_2][j_2] += 1$。操作过程中矩阵元素必须始终为非负整数。
希望经过若干次操作后得到一个矩阵 $B$，使得它同时满足”上下对称”和”左右对称”：对所有 $i, j$ 都有 $B[i][j] = B[n-1-i][j]$ 且 $B[i][j] = B[i][m-1-j]$。
输出任意一个满足条件的矩阵 $B$；如果不存在，输出 $-1$。
多组测试数据，所有测试数据的 $n \times m$ 之和不超过 $10^5$。
样例
输入
3
2 2
1 2
3 4
1 3
1 5 10
2 2
1 1
1 2
输出
-1
5 6 5
-1
思路分析
第一步：观察操作性质
每次操作将某格减 1、另一格加 1，矩阵总和 $S$ 始终不变。因此目标矩阵 $B$ 的总和必须等于原矩阵的总和。
第二步：对称把格子绑成组
上下对称要求 $B[i][j] = B[n-1-i][j]$，左右对称要求 $B[i][j] = B[i][m-1-j]$。两条约束合在一起，位置 $(i, j)$ 必须等于它的水平镜像、垂直镜像和对角镜像——这四个位置组成一组，组内必须取同一个值。
组的大小取决于位置：
- 正中心格（$n$ 和 $m$ 都奇时才存在）：三个镜像都是自己，独占一组（大小 1）
- 中线上的非中心格（$n$ 奇时的中间行非中心列、$m$ 奇时的中间列非中心行）：两个一组（大小 2）
- 其余格子：四个镜像互不相同，四个一组（大小 4）
第三步：判断有解条件
总和 $S$ 必须能被最小组整除：
- $n$、$m$ 都奇：有大小 1 的组，$S$ 直接塞进去——永远有解
- 恰一维为奇：最小组大小 2，$S$ 必须为偶数
- 都为偶：所有组大小 4，$S$ 必须是 4 的倍数
第四步：构造方案
把整张图的总和全部集中到最小组，其余格子全填 0：
- 都奇：$S$ 放在中心格
- 一奇一偶：$S/2$ 放在中心行或中心列的两端（它们是同组的镜像伙伴）
- 都偶：$S/4$ 放在四个角
题解代码
import sys
input = sys.stdin.readline
def solve():
T = int(input())
out = []
for _ in range(T):
n, m = map(int, input().split())
total = 0
for i in range(n):
row = list(map(int, input().split()))
total += sum(row)
n_odd = n % 2 == 1
m_odd = m % 2 == 1
if n_odd and m_odd:
cr, cc = n // 2, m // 2
for i in range(n):
row = []
for j in range(m):
row.append(str(total if i == cr and j == cc else 0))
out.append(" ".join(row))
elif n_odd or m_odd:
if total % 2 != 0:
out.append("-1")
continue
half = total // 2
for i in range(n):
row = []
for j in range(m):
v = 0
if n_odd and i == n // 2 and (j == 0 or j == m - 1):
v = half
elif m_odd and j == m // 2 and (i == 0 or i == n - 1):
v = half
row.append(str(v))
out.append(" ".join(row))
else:
if total % 4 != 0:
out.append("-1")
continue
q = total // 4
for i in range(n):
row = []
for j in range(m):
v = 0
if (i == 0 or i == n - 1) and (j == 0 or j == m - 1):
v = q
row.append(str(v))
out.append(" ".join(row))
print("\n".join(out))
solve()
复杂度分析
时间复杂度：$O(n \times m)$，读入矩阵并输出结果。 空间复杂度：$O(n \times m)$，输出缓冲。
第三题：弹性分桶
题目描述
给定 $n$ 个非负整数，可以重排这些数，再将它们划分为若干”桶”。设某个桶中含 $k$ 个数，最大值为 $\text{max}$、最小值为 $\text{min}$，则该桶必须满足两个约束：$k \leq L$，且 $\text{max} - \text{min} \leq D + E \cdot (k-1)$。
目标：使桶的总数最少。
样例
输入
2
7 3 1 3
1 2 3 7 8 10 10
7 0 0 5
5 5 5 6 6 6 6
输出
3
2
思路分析
第一步：观察题目性质
可以任意重排，所以最优桶一定是排序后的连续段——取同样数量的元素时，从最小值开始连续取一定不会比跳着取更糟。
排序后设某个桶覆盖 $a[i..j]$，桶大小 $k = j - i + 1$，约束变成：$k \leq L$ 且 $a[j] - a[i] \leq D + E \cdot (j - i)$。
第二步：为什么贪心不正确
直觉上”第一个桶尽量长”看似最优，但当 $D$ 和 $E$ 都非零时，延长首桶会让后段裕量收缩，整体可能反而更亏。必须用动态规划。
第三步：DP 设计
定义 $f[k]$ 表示把前 $k$ 个元素分桶的最少桶数。初始 $f[0] = 0$。
转移：枚举最后一个桶的左端 $i$，$f[j+1] = \min(f[i] + 1)$，其中 $i$ 需满足 $j - i + 1 \leq L$ 且 $a[j] - a[i] \leq D + E \cdot (j-i)$。
直接枚举每个 $j$ 的合法 $i$ 是 $O(n^2)$，超时。
第四步：关键变换——解耦下标
约束 $a[j] - a[i] \leq D + E \cdot (j-i)$ 把下标 $i$ 和 $j$ 同时耦合在右边。移项得：
\[a[j] - E \cdot j \leq a[i] - E \cdot i + D\]定义新数组 $b[k] = a[k] - E \cdot k$，约束化为 $b[i] \geq b[j] - D$。现在 $j$ 的部分凝结成阈值，$i$ 的合法性只看自己的 $b[i]$。
第五步：滑窗 + 线段树优化
每个 $j$ 要在窗口 $[j-L+1, j]$（长度限制）内找 $b[i] \geq b[j] - D$ 且 $f[i]$ 最小的 $i$。
把每个位置按 $b$ 值升序排成一排，分配给线段树的叶子。进窗时把对应叶子置为 $f[i]$，出窗时置回 $\infty$。查询时先二分找出叶子序列中第一个 $b$ 值 $\geq b[j] - D$ 的位置，从那往后做区间 $\min$。
每个 $j$ 的插入、删除、查询都是 $O(\log n)$。
题解代码
import sys
from bisect import bisect_left
input = sys.stdin.readline
INF = 10 ** 18
def solve():
n, D, E, L = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b = [a[i] - E * i for i in range(n)]
order = sorted(range(n), key=lambda i: (b[i], i))
pos_to_rank = [0] * n
for r, i in enumerate(order):
pos_to_rank[i] = r
sorted_b = [b[i] for i in order]
size = 1
while size < max(n, 1):
size *= 2
seg = [INF] * (2 * size)
def update(rk, val):
rk += size
seg[rk] = val
rk //= 2
while rk:
nv = min(seg[2 * rk], seg[2 * rk + 1])
if seg[rk] == nv:
break
seg[rk] = nv
rk //= 2
def query(lo, hi):
res = INF
lo += size
hi += size + 1
while lo < hi:
if lo & 1:
if seg[lo] < res:
res = seg[lo]
lo += 1
if hi & 1:
hi -= 1
if seg[hi] < res:
res = seg[hi]
lo >>= 1
hi >>= 1
return res
f = [INF] * (n + 1)
f[0] = 0
for j in range(n):
if j - L >= 0:
update(pos_to_rank[j - L], INF)
update(pos_to_rank[j], f[j])
thr = b[j] - D
lo_idx = bisect_left(sorted_b, thr)
if lo_idx < n:
res = query(lo_idx, n - 1)
if res < INF:
f[j + 1] = res + 1
return f[n]
T = int(input())
out = []
for _ in range(T):
out.append(str(solve()))
print("\n".join(out))
复杂度分析
时间复杂度：$O(n \log n)$，排序 + 每个位置在线段树上做常数次 $O(\log n)$ 操作。 空间复杂度：$O(n)$，DP 数组与线段树都线性于 $n$。
小结
- 第一题（平稳风段）：经典的最长合法连续段问题，判定条件仅涉及相邻元素，一次线性扫描即可，是稳拿的签到题。
- 第二题（正整数矩阵）：关键洞察是操作守恒总和，而对称约束将格子绑成固定大小的组。有解条件完全由总和与组大小的整除关系决定，构造方案只需集中放置。
- 第三题（弹性分桶）：排序后转化为连续段划分的 DP。核心技巧是通过 $b[k] = a[k] - E \cdot k$ 变换解耦双下标约束，再用线段树维护滑动窗口内满足阈值条件的最小 $f$ 值，将复杂度从 $O(n^2)$ 优化到 $O(n \log n)$。