大厂真题 / 华为
华为 7.24 笔试真题 - 研发岗
本场考试概述
考试时间：2026年7月24日
考试岗位：研发岗
难度评级：中等
考点分析：
- 第一题：二分答案 + 贪心统计（难度简单）
- 第二题：状态压缩 + Gray Code 枚举（难度中等）
- 第三题：动态规划 + 滚动数组（难度中等）
建议策略：
- 第一题先写出达到指定高度所需的总土方和总成本，再利用可行性的单调性二分最高高度
- 第二题的商品数不超过 $20$，可以枚举全部子集；用 Gray Code 让相邻子集只增删一件商品，避免每个子集重新统计
- 第三题必须同时记录“已经走了几步”和“当前落在哪块石板”；用两行滚动数组即可把空间降到 $O(n)$
第 1 题：最优河堤加固方案
题目描述
一段河堤被划分为 $n$ 段，第 $i$ 段当前高度为 $h_i$。现在可以向任意河堤段填土，每填入 $1$ 单位土，该段高度增加 $1$。为了让河堤整体达到同一防洪标准，要求所有河堤段的最终高度都不低于某个整数 $H$。
运输车辆每车最多装载 MaxCapacity 单位土，只要使用一车，不论是否装满，都要支付 TransportationCostPerShipment 的运输费用；此外，每填埋 $1$ 单位土还要支付 UnitCost。若共需要 total_soil 单位土，总成本为：
在总成本不超过 MaxCosts 的前提下，求所有河堤段都能达到的最大整数高度。
输入依次为：
- 第一行：预算
MaxCosts - 第二行：每车最大容量
MaxCapacity - 第三行：每车运输成本
TransportationCostPerShipment - 第四行：单位土填埋成本
UnitCost - 第五行：河堤段数 $n$
- 第六行：$n$ 个整数 $h_i$
数据范围：
- $0 \leq \text{MaxCosts} \leq 10^{10}$
- $1 \leq \text{MaxCapacity} \leq 100$
- $0 \leq \text{TransportationCostPerShipment} \leq 100$
- $1 \leq \text{UnitCost} \leq 100$
- $1 \leq n \leq 10^5$
- $0 \leq h_i \leq 10^6$
样例
输入
100
10
5
2
5
1 2 5 3 4
输出
11
思路分析
第一步：检查一个目标高度是否可行
假设目标高度为 $H$。高度已经不低于 $H$ 的河堤段无需处理，其余河堤段需要补到 $H$，因此总土方为：
\[S(H)=\sum_{i=0}^{n-1}\max(0,H-h_i)\]对应成本为：
\[C(H)=S(H)\times U+\left\lceil\frac{S(H)}{M}\right\rceil\times T\]其中 $U$ 是单位填埋成本，$M$ 是车辆容量，$T$ 是单车运输成本。整数除法可把向上取整写成 (soil + capacity - 1) // capacity。
统计土方时，一旦当前土方对应的成本已经超过预算，就可以提前返回，不必继续扫描。
第二步：发现单调性
随着目标高度 $H$ 增大，所需土方不会减少，总成本也不会减少。因此：
- 若高度 $H$ 可行，则所有不高于 $H$ 的高度都可行
- 若高度 $H$ 不可行，则所有高于 $H$ 的高度都不可行
这正是二分答案需要的单调性。
第三步：确定二分边界
不填土时，所有河堤至少能达到 min(heights)，所以它是一个可行下界。
每增加一单位最低防洪标准，至少需要向某一段填入一单位土；又因为 UnitCost >= 1，目标高度最多比当前最高河堤高 MaxCosts // UnitCost。因此可以把开区间右端点设为：
max(heights) + MaxCosts // UnitCost + 1
维护“左端点可行、右端点不可行”的开区间，最终左端点就是答案。
样例校验：目标高度为 $11$ 时，需要的土方为 $10+9+6+8+7=40$，需要 $4$ 车，总成本为 $40\times2+4\times5=100$，恰好不超过预算；目标高度为 $12$ 时需要 $45$ 单位土、$5$ 车，总成本为 $115$，因此最大高度为 $11$。
题解代码
import sys
input = sys.stdin.buffer.readline
def solve():
max_costs = int(input())
max_capacity = int(input())
transportation_cost = int(input())
unit_cost = int(input())
n = int(input())
heights = list(map(int, input().split()))
def feasible(target):
soil = 0
for height in heights:
if height < target:
soil += target - height
shipments = (soil + max_capacity - 1) // max_capacity
cost = soil * unit_cost + shipments * transportation_cost
if cost > max_costs:
return False
return True
left = min(heights)
right = max(heights) + max_costs // unit_cost + 1
while left + 1 < right:
middle = (left + right) // 2
if feasible(middle):
left = middle
else:
right = middle
print(left)
solve()
复杂度分析
设二分答案范围为 $V$。
时间复杂度：$O(n\log V)$，每次可行性检查最多扫描 $n$ 段河堤。
空间复杂度：额外空间为 $O(1)$，只使用常数个辅助变量；若计入存储输入高度数组的空间，则为 $O(n)$。
第 2 题：双 11 购物狂欢
题目描述
双 11 期间有 $n$ 件商品可供选择，每件商品包含四项信息：商品编号 id、商品类别 category、原价 price 和满意度 satisfaction。每件商品至多购买一次，商品编号只用于标识，不影响优惠和满意度。
选好商品后，先计算商品原价总和 $P$，再根据所选商品中不同类别的数量计算满减：
- 不同类别数小于 $3$：每满 $200$ 元减 $20$ 元
- 不同类别数不少于 $3$：每满 $200$ 元减 $30$ 元
满减次数为 $\lfloor P/200\rfloor$，不足 $200$ 的部分不参与满减。付款金额不能超过预算 budget，求能够获得的最大满意度。允许不购买任何商品，此时满意度为 $0$。
输入格式：
- 第一行：预算
budget - 第二行：商品数量 $n$
- 接下来 $n$ 行：
id category price satisfaction
数据范围：
- $10 \leq \text{budget} \leq 1000$
- $1 \leq n \leq 20$
price、satisfaction均为非负整数category为不含空格的字符串
样例
输入
200
4
1001 food 100 100
1002 food 100 100
1003 digital 200 230
1004 clothes 230 240
输出
230
思路分析
第一步：根据 $n\leq20$ 枚举子集
每件商品只有“买”和“不买”两种选择，所有购物方案一共有 $2^n$ 个。$2^{20}=1048576$，完整枚举可以接受。
对于一个子集，需要知道：
- 原价总和
- 满意度总和
- 每个类别出现了多少次，从而得到不同类别数
算出不同类别数后即可按规则计算满减和实付款，再检查是否超过预算。
第二步：为什么不直接为每个掩码扫描全部商品
若对每个子集都重新扫描 $n$ 件商品，时间复杂度为 $O(n2^n)$。虽然上界仍可能通过，但 Python 中会进行约两千万次位判断，而且为每个掩码保存价格、满意度和类别集合也会产生较大的内存开销。
可以改为按 Gray Code 顺序枚举。第 $i$ 个 Gray Code 为：
gray = i ^ (i >> 1)
相邻两个 Gray Code 恰好只有一个二进制位不同。因此每次只会增加或删除一件商品，可以在 $O(1)$ 时间内更新总价与总满意度，并用类别计数数组维护不同类别数。
第三步：计算实付款
设当前不同类别数为 category_count：
reduction = 20 if category_count < 3 else 30
payment = total_price - (total_price // 200) * reduction
若 payment <= budget，就用当前满意度更新答案。
样例校验：单独购买编号 1003 的商品，原价为 $200$，所选类别数为 $1$，满 $200$ 减 $20$，实际支付 $180$，满意度为 $230$。其他预算内方案的满意度都不超过 $230$，所以答案为 $230$。
题解代码
import sys
input = sys.stdin.buffer.readline
def solve():
budget = int(input())
n = int(input())
category_id = {}
prices = [0] * n
satisfactions = [0] * n
categories = [0] * n
for i in range(n):
_, category, price, satisfaction = input().split()
if category not in category_id:
category_id[category] = len(category_id)
categories[i] = category_id[category]
prices[i] = int(price)
satisfactions[i] = int(satisfaction)
frequency = [0] * len(category_id)
category_count = 0
total_price = 0
total_satisfaction = 0
answer = 0
previous_gray = 0
for number in range(1, 1 << n):
gray = number ^ (number >> 1)
changed = gray ^ previous_gray
item = changed.bit_length() - 1
category = categories[item]
if gray & changed:
total_price += prices[item]
total_satisfaction += satisfactions[item]
if frequency[category] == 0:
category_count += 1
frequency[category] += 1
else:
total_price -= prices[item]
total_satisfaction -= satisfactions[item]
frequency[category] -= 1
if frequency[category] == 0:
category_count -= 1
reduction = 20 if category_count < 3 else 30
payment = total_price - (total_price // 200) * reduction
if payment <= budget and total_satisfaction > answer:
answer = total_satisfaction
previous_gray = gray
print(answer)
solve()
复杂度分析
时间复杂度：$O(2^n)$，Gray Code 相邻状态只需更新一件商品。
空间复杂度：$O(n+C)$，其中 $C$ 为不同商品类别数；无需保存全部 $2^n$ 个子集状态。
第 3 题：地宫探宝
题目描述
地宫中从左到右排列着 $n$ 块石板，第 $i$ 块石板上有价值为 $v_i$ 的宝物。探险者最初位于第一块石板之前，每一步只能向右移动 $1$、$2$ 或 $3$ 块石板；每次落到一块石板上，就会获得该石板上的宝物，宝物不会重复获得。
探险者必须在不超过 $m$ 步内落到最后一块石板，求最多能够获得的宝物总价值。题目保证存在合法方案。
输入格式：
- 第一行：石板数量 $n$ 和最大步数 $m$
- 第二行：$n$ 个整数 $v_i$
数据范围：
- $5 \leq n \leq 10^4$
- $2 \leq m \leq 5000$
- $0 \leq v_i \leq 5$
样例
输入
5 3
1 2 1 1 3
输出
6
思路分析
第一步：设计状态
设 dp[s][i] 表示恰好走 $s$ 步并落在第 $i$ 块石板时，最多能获得的宝物价值。最后一步可能从前面的第 $i-1$、$i-2$ 或 $i-3$ 块石板跳来，因此：
起点位于石板数组之外，可视为下标 $-1$。从起点第一步可以落到下标 $0$、$1$、$2$，所以第一步的这三个状态分别为对应石板的价值。
第二步：把“至多 $m$ 步”化为一个确定步数
每步至少前进一块，因此最多只能走 $n$ 步；允许使用的最大步数为：
\[k=\min(m,n)\]由于宝物价值均为非负数，把一次长度为 $2$ 或 $3$ 的跳跃拆成多次更短跳跃，不会丢失原来落点上的宝物，只会多经过一些价值非负的石板。因此，在能够到达终点的前提下，使用更多步数所得最优值不会更小。
所以“至多 $m$ 步”的最优方案一定可以取恰好 $k$ 步，只需计算 dp[k][n - 1]。若题目允许负价值，这个结论将不再成立，届时需要对所有不超过 $m$ 的步数取最大值。
第三步：滚动数组降低内存
第 $s$ 层只依赖第 $s-1$ 层，不必保存完整的 $m\times n$ 状态表。用 previous 和 current 两个长度为 $n$ 的数组滚动，空间复杂度可降为 $O(n)$。
另外，走 $s$ 步后能到达的下标范围是：
\[s-1\leq i\leq 3s-1\]循环时只枚举这个范围与 $[0,n-1]$ 的交集，可以跳过显然不可达的位置。
样例校验：可以依次跳到下标 $1$、$3$、$4$，步长为 $2,2,1$，获得价值 $2+1+3=6$；不存在价值更大的三步方案，因此输出 $6$。
题解代码
import sys
input = sys.stdin.buffer.readline
def solve():
n, m = map(int, input().split())
values = list(map(int, input().split()))
steps = min(m, n)
negative_infinity = -10**18
# 第一步可从起点落到下标 0、1、2。
previous = [negative_infinity] * n
for i in range(min(3, n)):
previous[i] = values[i]
for step in range(2, steps + 1):
current = [negative_infinity] * n
left = step - 1
right = min(n - 1, 3 * step - 1)
for i in range(left, right + 1):
best_previous = previous[i - 1]
if i >= 2 and previous[i - 2] > best_previous:
best_previous = previous[i - 2]
if i >= 3 and previous[i - 3] > best_previous:
best_previous = previous[i - 3]
if best_previous != negative_infinity:
current[i] = best_previous + values[i]
previous = current
print(previous[n - 1])
solve()
复杂度分析
令 $k=\min(m,n)$。
时间复杂度：$O(nk)$；利用可达范围后实际遍历的状态通常更少。
空间复杂度：$O(n)$，使用两个长度为 $n$ 的滚动数组。
小结
- 第一题先将目标高度转化为总土方和总成本，再利用可行性的单调性二分最大高度；样例中高度 $11$ 恰好耗尽预算
- 第二题利用 $n\leq20$ 枚举所有购物子集，Gray Code 能在常数时间更新相邻子集，并把额外空间控制在线性级别
- 第三题用“步数 + 落点”建立动态规划；宝物价值非负保证最优方案可以使用允许的最大步数，两行滚动数组则避免了 $O(nm)$ 的内存开销