华为机考（非 AI 方向）真题解析：双十一凑单与优惠券的最少实付

《面试题目》

1. 购物车里有 a 件必须买的货物和 b 件可买可不买的凑单货物，另有 c 张优惠券（每张给出类型 f、启用门槛 g、面额或折扣百分比 d），如何选择凑单组合与用券方案，使结账时的实付金额最小？
2. 减钱券（f = 0）和打折券（f = 1）分别怎样改变订单现价？
3. 优惠券的启用有哪些约束？（每张至多启用一次、可以整张弃用、启用顺序可自行排列；套用它的前一刻现价必须 ≥ g；一张券生效后的新现价是后续券的对照基准）
4. 输入怎么给？凑单件数 b = 0 时输入有什么不同？
5. 输出要求是什么？
6. 样例中必买 1 件 100 元、凑单 1 件 20 元，两张券分别是「现价 ≥ 100 打 5 折」和「现价 ≥ 50 减 10 元」，为什么最少实付是 40 元？

---

《参考解析》

为什么这道题不能只靠贪心

券的启用门槛让决策互相牵制：一张券能不能用，取决于前面已经套过哪些券、当前现价是多少，所以「先减钱还是先打折」没有固定答案；凑单货也不是一律不加更省——有时候加一件小额凑单货刚好凑过门槛，实付反而更低。a、b、c 的量级都很小（凑单件数 b ≤ 10、券数 c ≤ 5），正解是把所有可能的方案枚举完取最小值。

枚举结构：凑单子集 × 用券子集 × 券序排列

• 先把 a 件必买货的标价求和，作为基准现价；不加任何凑单货、不用任何券就是它。
• 用二进制枚举 b 件凑单货的全部子集，得到这一种购物车对应的订单现价（b = 0 时只有「不加」一种）。
• 对这个现价，再枚举 c 张券的全部子集，并对每个子集做全排列——空子集代表一张券都不用。券的枚举必须带排列，因为顺序不同结算结果不同。
• 按一种次序逐张套用：现价低于门槛就跳过这一张，继续看后面的券（跳过不等于退出）；f = 0 时现价减去 d，f = 1 时现价改成 floor(现价 × d / 100)。
• 全部试完后现价若为负，按 0 记；在所有组合与次序里取最小值。

for 凑单子集:
    total = 必买标价之和 + 选中的凑单标价
    for 用券子集:
        for 该子集的每个排列 order:
            price = total
            for 券 in order:
                if price < 券.g: continue
                price = 券.f == 0 ? price - 券.d : price * 券.d / 100
            best = min(best, max(price, 0))

一个有用的直觉：先打折、后满减一般不会更差

设套券前的现价为 P，另有折扣比例 d（%）与满减金额 c：先打折再减钱得 P·d/100 − c，先减钱再打折得 (P − c)·d/100 = P·d/100 − c·d/100，两者相差 c·(d/100 − 1) ≤ 0（d ≤ 100），所以把打折券排在满减券之前，结果不会变大。这个结论可以用来自查枚举结果，但替代不了枚举——门槛 g 会让「哪张券在那一刻用得上」随顺序变化，贪心排法未必可行。

实现上的几个坑

• 打折是向下取整（floor），不是四舍五入；现价非负时整数除法（price * d / 100）正好是 floor 语义，用浮点乘再转整数则容易在边界上差 1。
• 结算过程要用 64 位整数，标价与折扣相乘那一步容易溢出 int。
• 门槛比较用的是套用前一刻的现价，所以要按顺序边算边判，不能预先筛一遍券。
• 同一张券不能重复用，但允许「有券没用」；被跳过的券留在序列后面，仍可能在后续现价变化后生效。

复杂度

外层枚举 2^b 个凑单子集，内层对每种用券方案做全排列，每种排列最多扫 c 张券，时间复杂度 O(2^b · Σ C(c,i) · i! · i)；空间只需保存标价、券与当前排列，O(a + b + c)。样例中不加凑单、两张券都启用，顺序取「先打折（100 → 50）再减钱（50 → 40）」，实付 40 元即最小值。