大厂真题 / 网易雷火
网易雷火 4.2 笔试真题 - 研发岗
本场考试概述
考试时间：2026年4月2日 考试岗位：研发岗 难度评级：中等偏难
考点分析：
- 第一题：贪心（难度中等）
- 第二题：模拟（难度中等）
- 第三题：二分答案（难度困难）
- 第四题：模拟（难度困难）
建议策略：
- 前两题贪心和模拟较为友好，务必拿满分
- 第三题二分答案是本场核心难点，需要理解 check 函数的构造方式
- 第四题系统模拟逻辑复杂，考场时间有限可优先保前三题
第一题：沙场点兵
题目描述
辽军派出 n 支小队，出战顺序固定。作为宋军指挥官，你手下也有 n 支小队，可自由排列。每轮双方各派一支小队对决，战力高者获胜（相同战力辽军获胜）。判断是否存在方案使我军胜场数严格过半。
样例
输入
2
5
2 5 7 1 6
3 5 6 2 7
3
3 3 3
3 3 3
输出
YES
NO
题解：贪心（田忌赛马）
将我军和辽军战力均升序排序。维护两个指针：hi 指向我方最强，lo 指向最弱；从对方最强开始逐个处理。若我方最强能赢对方最强，就匹配；否则用最弱的去消耗这场，保留强者对付后续。
时间复杂度：O(n log n)。 空间复杂度：O(n)。
import sys
input = sys.stdin.readline
def solve():
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
win = 0
lo = 0
hi_a = n - 1
hi_b = n - 1
while hi_b >= lo:
if a[hi_a] > b[hi_b]:
win += 1
hi_a -= 1
else:
lo += 1
hi_b -= 1
return "YES" if win > n // 2 else "NO"
T = int(input())
out = []
for _ in range(T):
out.append(solve())
print("\n".join(out))
第二题：背包排序
题目描述
玩家有一个 n x m 的背包网格和 t 个物品。先按规则排序，然后按顺序逐个放入背包（优先行小、列小的位置）。物品属性包括 id、h x w（占用尺寸）、quality（品质）、type（种类）。排序规则：type 优先级（equip > weapon > item > other），品质高优先，id 小优先。输出能否放下所有物品及最终网格状态。
样例
输入
4 3 3
1 1 3 7 other
2 3 1 2 equip
3 2 2 4 other
输出
YES
2 3 3
2 3 3
2 0 0
1 1 1
题解：模拟
数据规模不大，直接模拟。排序后逐个放置，对每个物品遍历所有可能的左上角位置，找到第一个能放下的位置填入。
时间复杂度：O(t * n * m * h * w)。 空间复杂度：O(n * m)。
import sys
input = sys.stdin.readline
def type_order(s):
return {"equip": 0, "weapon": 1, "item": 2, "other": 3}.get(s, 3)
def main():
n, m, t = map(int, input().split())
items = []
for _ in range(t):
parts = input().split()
uid, h, w, q = int(parts[0]), int(parts[1]), int(parts[2]), int(parts[3])
tp = parts[4]
items.append((type_order(tp), -q, uid, h, w))
items.sort()
grid = [[0] * m for _ in range(n)]
all_placed = True
for _, _, uid, h, w in items:
placed = False
for r in range(n - h + 1):
for c in range(m - w + 1):
ok = all(grid[r + dr][c + dc] == 0 for dr in range(h) for dc in range(w))
if ok:
for dr in range(h):
for dc in range(w):
grid[r + dr][c + dc] = uid
placed = True
break
if placed:
break
if not placed:
all_placed = False
print("YES" if all_placed else "NO")
for row in grid:
print(" ".join(map(str, row)))
main()
第三题：不朽荣光
题目描述
索桥安全区域为 [0, L]，桥上有 n 名敌人，坐标 x_i。每次射击选落点 p：命中 p 处的敌人直接淘汰，p 左侧敌人向左推 r 格，p 右侧敌人向右推 r 格。推出边界即淘汰。求最少射击次数。
样例
输入
3 10 2
3 5 9
输出
2
题解：二分答案
二分射击次数 k，判断 k 次是否足够。将敌人坐标排序后，前 a 个从左边界推下（需 x_i ≤ kr），中间 k 个直接命中，剩余从右边界推下（需 x_i ≥ L - kr）。用 upper_bound 找出满足左推条件的最大 a 值，检查右侧是否满足。
时间复杂度：O(n log n)。 空间复杂度：O(n)。
import sys
from bisect import bisect_right
input = sys.stdin.readline
def main():
n, L, r = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
push_left = mid * r
push_right = L - mid * r
a = bisect_right(x, push_left)
idx = a + mid
if idx >= n or push_right <= 0 or x[idx] >= push_right:
hi = mid
else:
lo = mid + 1
print(lo)
main()
第四题：贴图流式加载
题目描述
实现一个带 LRU 回收机制的贴图流式加载系统。每张贴图有多级 mip，每级占用显存为上一级的 1/4。支持加载请求和主动清理信号，显存不足时按过期时间升序回收，输出所有状态变化日志。
样例
输入
120 4 7
1 3 0 20 1
1 2 0 40 2
1 1 0 40 2
1 4 0 20 1
5 4 0 20 1
6 4 0 20 1
99 -1
输出
1 3 0 20
1 2 0 70
1 1 0 120
6 1 -1 70
6 4 0 90
99 2 -1 40
99 3 -1 20
99 4 -1 0
题解：模拟
规模较小但规则复杂，用字典维护每个贴图的 mip 加载状态和过期时间，严格按规则执行。
时间复杂度：O(N * K * log K)，其中 K 是活跃贴图数量。 空间复杂度：O(K * C)。
import sys
input = sys.stdin.readline
def mip_size(s, level):
sz = s
for _ in range(level):
sz //= 4
return sz
def main():
M, D, N = map(int, input().split())
props = {}
mips_map = {}
used_vram = 0
result = []
for _ in range(N):
parts = input().split()
t = int(parts[0])
tid = int(parts[1])
if tid == -1:
to_remove = []
for rid in sorted(mips_map.keys()):
mips = mips_map[rid]
expired = [m for m, exp in mips.items() if exp < t]
if expired:
s, c = props[rid]
for m in expired:
used_vram -= mip_size(s, m)
del mips[m]
new_min = min(mips.keys()) if mips else -1
result.append(f"{t} {rid} {new_min} {used_vram}")
if not mips:
to_remove.append(rid)
for rid in to_remove:
del mips_map[rid]
del props[rid]
else:
X = int(parts[2])
s = int(parts[3])
c = int(parts[4])
props[tid] = (s, c)
if tid not in mips_map:
mips_map[tid] = {}
mips = mips_map[tid]
need_load = [m for m in range(X, c) if m not in mips]
extra = sum(mip_size(s, m) for m in need_load)
if extra > 0 and used_vram + extra > M:
cands = []
for rid, rmips in mips_map.items():
for m, exp in rmips.items():
if exp < t and not (rid == tid and m >= X):
cands.append((exp, rid, m))
cands.sort()
groups = {}
for exp, rid, m in cands:
key = (exp, rid)
if key not in groups:
groups[key] = []
groups[key].append(m)
for key in sorted(groups.keys()):
if used_vram + extra <= M:
break
exp, rid = key
rs, rc = props[rid]
rmips = mips_map[rid]
for m in groups[key]:
used_vram -= mip_size(rs, m)
del rmips[m]
new_min = min(rmips.keys()) if rmips else -1
result.append(f"{t} {rid} {new_min} {used_vram}")
if used_vram + extra > M:
empty = [rid for rid, rmips in mips_map.items() if not rmips]
for rid in empty:
del mips_map[rid]
del props[rid]
continue
if extra > 0:
for m in need_load:
mips[m] = t + D
used_vram += mip_size(s, m)
for m in list(mips.keys()):
mips[m] = t + D
if extra > 0:
new_min = min(mips.keys())
result.append(f"{t} {tid} {new_min} {used_vram}")
empty = [rid for rid, rmips in mips_map.items() if not rmips]
for rid in empty:
del mips_map[rid]
del props[rid]
print("\n".join(result))
main()
小结
- 第一题贪心（田忌赛马），将双方排序后双指针分配对局，O(n log n) 即可
- 第二题模拟（背包排序），按多关键字排序后逐个放置矩形物品
- 第三题二分答案是本场核心难点，关键在于将敌人分为左推、直接命中、右推三组
- 第四题贴图流式加载规则复杂但数据规模不大，仔细处理 LRU 回收和日志输出即可