DoorDash 购物车最优优惠：百分比、固定额与运费边界

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 可见题目未明确固定额优惠是否能抵扣运费、是否叠加多张券、是否有最低消费。训练契约选择一次只用一张券，固定额可抵商品加运费的总额但总付款不低于零；面试时先确认。
• 金额用非负整数 cents，百分比是 0–100 的整数；折扣结果按 half-up 四舍五入到最小货币单位。题目未明确舍入规则。
• 若没有优惠或所有优惠都不降低价格，返回无优惠；多张优惠同价时保留输入顺序最早的一张。

解题路线

1. 先求商品小计 S 与运费 H，总价 T=S+H。逐张验证券类型和数值，百分比折扣只从 S 计算，固定额折扣从 T 扣并以 T 为上限。
2. 比较每张券应用后的应付金额；只有严格更低才更新 winner，因此自然实现最早同价券胜出。
3. 把百分比作用范围、固定额作用范围、最低消费、叠加与舍入写成独立政策函数，真实生产代码可随题目分段逐步扩展。

手动走一遍

商品 1000、500 cents，运费 200 cents；10% 券只优惠商品小计 150，付款 1550；固定 300 cents 券按训练契约抵全额，付款 1400，因此选固定券。若运费 200、商品 0，100% 券仍付 200，不会把运费抹掉。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""One-promotion cart pricing under an explicit training contract."""

from dataclasses import dataclass


@dataclass(frozen=True)
class Promotion:
    code: str
    kind: str  # "percent" or "fixed"
    amount: int  # percent 0..100, or fixed discount in cents


def best_payment(item_prices_cents: list[int], shipping_cents: int, promotions: list[Promotion]) -> tuple[str | None, int]:
    if shipping_cents < 0 or any(price < 0 for price in item_prices_cents):
        raise ValueError("prices must be nonnegative")
    subtotal = sum(item_prices_cents)
    total = subtotal + shipping_cents
    winner: str | None = None
    best_due = total
    for promo in promotions:
        if promo.kind == "percent":
            if not 0 <= promo.amount <= 100:
                raise ValueError("percent must be 0..100")
            # Round half up to cents; percent excludes shipping.
            discount = (subtotal * promo.amount + 50) // 100
        elif promo.kind == "fixed":
            if promo.amount < 0:
                raise ValueError("fixed discount must be nonnegative")
            # Training choice: fixed discount may reduce total including shipping.
            discount = min(total, promo.amount)
        else:
            raise ValueError("unknown promotion kind")
        due = total - discount
        if due < best_due:
            best_due, winner = due, promo.code
    return winner, best_due

复杂度

n 件商品、p 张券，求和及逐券比较为 O(n+p) 时间，除输入外 O(1) 额外空间；若要返回所有候选明细则为 O(p)。

易错点与追问

容易失分的边界

• 用浮点金额在百分比与付款相减时会产生分钱误差；以 cents/Decimal 和已确认的舍入规则计算。
• 把百分比乘总价会错误优惠运费；可读题目明确要求排除运费。
• 固定额可能超过总价，应截到总价，不能返回负付款；但固定额到底能否抵运费需向面试官确认，示例不能宣称唯一原题答案。
• 先按折扣面值比较券并不总等于按实际应付额比较，例如 100% 商品券在空购物车上没有优惠。

继续深挖

• 若允许多券叠加，要明确先百分比后固定额、互斥分组、使用次数和运费券规则；一般不能再直接取单张最大。
• 若要返回折扣明细，记录原价、小计折扣、运费折扣、税前/税后金额及所用规则版本，便于收据与争议处理。