华为机考(非 AI 方向):短语分栏排版与生鲜店七天订货计划
- 轮次
- 笔试
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 按格式排列短语(150 分):给定纸张单行最大宽度 W 与 M 条短语的长度,要求保持短语原有先后次序,从第一列起一列印满后才印下一列,同一列内短语靠左对齐,同一行相邻短语之间至少空一格,每行末尾不留空格。求印完全部短语最少需要多少行。
- 生鲜超市订货计划(150 分):连续经营 7 天,每天开门前可按当天进货价补货,当天未卖完的水果可留到第二天继续卖,但按当天仓储价对剩余公斤数计费。每天需求必须全部满足,第 1 天开门前仓库为空,第 7 天打烊后仓库必须清空,仓储费在当天结束时结算。单日补货量不能超过 1000 kg,若某天需求超过 1000 kg 直接输出 −1。求七天最低总支出。
《参考解析》
第一题的关键结论是「总宽度关于行数不单调」,所以只能枚举。 当行数为 k 时,短语按原顺序每 k 条组成一列(最后一列可以不足 k 条),每一列的宽度等于该列中最长短语的长度,列与列之间需要一个空格,因此总宽度 = 各列最大长度之和 + (列数 − 1)。样例 5 3 2 4 1 6、W = 12:k = 2 时按每 2 条一列切分成 (5,3)、(2,4)、(1,6),三列的最大长度为 5、4、6,总宽 5+4+6+2 = 17 > 12;k = 3 时分成 (5,3,2) 与 (4,1,6) 两列,总宽 5+6+1 = 12 ≤ 12,答案为 3。
为什么不能二分:k 增大时列数减少(空格变少),但每一列变长导致列内最大值可能变大,两者方向相反,总宽度随 k 变化并不单调。数据范围允许 O(M²),直接从小到大枚举 k、每次 O(M) 计算总宽即可;若 M 很大,可以预处理每列的最大值(滑动窗口或分块 RMQ)把单次计算降到 O(M/k),但本题规模下没有必要。边界:k = 1 时所有短语排成一列,宽度是该列最大值;若单条短语长度超过 W 则无解(题面保证存在可行解);最后一列不参与空格计数。
第二题是典型的「跨期持有成本」最小化,用优先队列做贪心。 把「第 j 天进货、留到第 i 天卖出」的每公斤成本写成 c_j + Σ_{t=j}^{i-1} s_t。令 P_i = Σ_{t<i} s_t(前 i−1 天的仓储价之和),则成本 = (c_j − P_j) + P_i。对固定的第 i 天,P_i 是常数,因此只需在所有可用的进货日里挑 c_j − P_j 最小的那个。按天从左到右推进:先把当天的报价 (c_i − P_i, 剩余额度 1000) 压入小根堆,再用堆顶依次满足当天的需求,每取一公斤就扣减该来源的剩余额度,额度用完则弹出。这样保证任何时刻都用「到目前为止最便宜的来源」,且每天的进货总量不超过 1000 kg。
为什么这个贪心正确:这是一个带容量的最小费用流问题,所有货源到所有需求日之间的成本满足「同一货源对不同需求日的成本差是固定的」,因此按单位成本排序后依次匹配不会破坏最优性(交换论证:若最优解用了更贵的来源而没用更便宜的,互换不增加总成本,且容量约束仍然满足)。第 7 天打烊后必须清空的约束,在模型里等价于「不购买超过七天总需求的量」,贪心按需求逐日取货天然满足。
两个易错点。 一是把 P_i 的起点写错(应当是前 i−1 天的仓储费之和,即第 i 天卖出时已经经历的天数);二是漏掉「单日需求超过 1000 kg 直接输出 −1」这一条,因为此时当天最多订 1000 kg,无论怎么安排都无法满足。样例数据里越晚进货越便宜,最优解就是每天按当天需求进货,总支出 5270。