题目重点：每项任务给两人分别有不同 reward，第一人必须承担恰好 K 项；用全给第二人的基线加前 K 个收益差，说明负收益也须选足。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每个任务恰好分给一人，不可拆分或不做；第一人恰好做 k 个，第二人承担剩余 n−k 个。奖励相加且任务之间没有依赖。
- 两个 reward 数组等长；k 为 0..n。训练代码允许负奖励，因为题目未限定非负；即使所有差值为负，也仍要让第一人做满 k 个。
解题路线
- 先假设所有任务都给第二人，得到 baseline=Σ reward_2[i]。把任务 i 改给第一人的净增益为 delta_i=reward_1[i]−reward_2[i]。
- 恰好选 k 个任务改派，所以只需取最大的 k 个 delta；结果是 baseline 加这些 delta 的和。排序全部差值后取前 k，或大规模且 k 很小时维护大小 k 的最小堆。
- 交换论证：若某最优分配选了 delta 较小的 i，却没选 delta 更大的 j，交换两者仍满足恰好 k 项且总奖励不减；反复交换可得到按差值取前 k 的解。
手动走一遍
reward_1=[8,4,6]、reward_2=[5,7,3]、k=2。全给第二人得 15；差值为 [3,−3,3]，取两个 3，最大值 21。若 k=3，必须把 −3 也选上，结果 18，不能因为是负差值就少分一个任务。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Assign exactly k tasks to worker A, remainder to B."""
def max_reward(reward_a: list[int], reward_b: list[int], k: int) -> int:
if len(reward_a) != len(reward_b):
raise ValueError("reward arrays must have the same length")
n = len(reward_a)
if not 0 <= k <= n:
raise ValueError("k must be between 0 and task count")
baseline = sum(reward_b)
improvements = sorted((a - b for a, b in zip(reward_a, reward_b)), reverse=True)
return baseline + sum(improvements[:k])
复杂度
计算差值 O(n)，排序 O(n log n) 时间、O(n) 额外空间；若 k≪n，用大小 k 的最小堆可做到 O(n log k) 时间、O(k) 空间。k=0 可直接返回 baseline。
易错点与追问
容易失分的边界
- 分别取第一人奖励最高的 k 项，却忽略这些任务交给第二人的机会成本；应按 reward_1−reward_2 排。
- 把‘必须完成 k 个’误成‘最多 k 个’，遇到负差值就跳过，违反恰好分配约束。
- 两个数组长度或 k 范围不合法时仍下标访问；先定义输入校验。
继续深挖
- 若第一人至少 k、至多 h 个，差值为正的项可多选，但必须满足下界；如何从排序前缀和中选最佳长度？
- 若每项任务有完成时间而两人各有工时容量，独立排序不再充分，可能转为背包或最小费用流。
- 如果新增第三个执行人且每人有固定任务数，怎样建模成分配/费用流问题？
