一维奶茶配送：先最大匹配数，再最小总距离

题意与假设

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

• 一维整数坐标，每店能送一杯、每人收一杯；距离上限D默认5。
• 优先最大配送人数，再最小距离总和；不是先选全局最近pair，输出(count,cost)不含具体配对。

解题路线

1. 排序两侧。绝对距离满足非交叉交换不增加总成本；若交叉两对都距离≤D，交换后两对仍在同一限距内。因此存在非交叉最优匹配。
2. dp[i,j]为前i人前j店最优(count,−cost)，候选跳过人、跳过店、在限距内配当前二者并加一单/减距离。lex max严格保持第一目标。
3. 滚动行O(S)空间。要重建配对需保留choice或分治复原。一般二维坐标没有同一非交叉排序保证，应改最小费用最大流/匹配，不能照搬1D DP。

手动走一遍

people=[0,4],shops=[3,7]，D5：最近全局4→3若先抢会让0无法匹配7，只一单；最优0→3、4→7，两单总距6。只一个人0、店−4与1，最大数都1，第二目标选择距1。

Python 参考实现

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

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

def best_delivery(people,shops,limit=5):
    if limit<0:raise ValueError("nonnegative distance limit required")
    people,shops=sorted(people),sorted(shops)
    previous=[(0,0)]*(len(shops)+1)
    for person in people:
        current=[(0,0)]
        for j,shop in enumerate(shops,1):
            best=max(previous[j],current[j-1])
            distance=abs(person-shop)
            if distance<=limit:
                count,negative_cost=previous[j-1]
                best=max(best,(count+1,negative_cost-distance))
            current.append(best)
        previous=current
    count,negative=previous[-1]
    return count,-negative

复杂度

P人S店，排序O(PlogP+SlogS)，DP O(PS)时间/O(S)空间。大输入需进一步利用区间/Monge结构或明确规模，不声称此法线性。

易错点与追问

容易失分的边界

• 普通最大匹配只保证人数不保证最小距离。
• 先按距离贪心可牺牲第一目标。

继续深挖

• 每店容量多杯怎样建有容量匹配？
• 返回实际配对时如何记录skip/match并处理稳定tie？