更新题目 两种技能各 K 人最小成本
题目 visa-two-skill-min-cost-team · 修改（rev 3） · · 2026-10-26 23:11
body
@@ -1,5 +1,23 @@ ## 题目 -有 n 个人，每人有一个费用，并且会技能 1 和技能 2 里的零种、一种或两种。选出一些人，要求选中的人里至少 K 个会技能 1、至少 K 个会技能 2，费用总和最小。对 K = 1 到 n 每个都求一次答案，返回一个数组；做不到的 K 填 -1。 +有 n 个人，每人有一个费用，并且会技能 1 和技能 2 里的零种、一种或两种。选出一些人，要求选中的人里至少 K 个会技能 1、至少 K 个会技能 2，费用总和最小。对 K = 1 到 n 每个都求一次答案，返回一个数组，做不到的 K 填 -1。 + +两种技能都会的人，在「会技能 1 的人数」和「会技能 2 的人数」里各算一次，这是按上面的题面读出来的（原帖原话未核实）。 + +下面假设费用都不为负（现有记录里没写费用范围，未核实）。费用可以为负时，「至少 K 个」允许多选，负费用的人不管会不会技能都该全选进来，下面的做法就不对了。例如 `[(两种都会, 3), (都不会, -5)]`，K = 1 的最优是两人都选，共 -2，下面的做法给出 3。 + +例子：7 个人，`(技能, 费用)` 分别是 + +| 人 | 技能 | 费用 | +| --- | --- | --- | +| P0 | 1 和 2 | 7 | +| P1 | 只会 1 | 1 | +| P2 | 只会 1 | 4 | +| P3 | 只会 2 | 2 | +| P4 | 只会 2 | 9 | +| P5 | 都不会 | 0 | +| P6 | 1 和 2 | 5 | + +答案是 `[3, 8, 15, 28, -1, -1, -1]`。K = 1 选 P1 和 P3（1 + 2 = 3），比单选一个两种都会的 P6（5）便宜。K = 2 在此基础上加 P6，共 8。K = 3 再加 P0，共 15。K = 4 再加 P2 和 P4，共 28。会技能 1 的一共只有 4 人，K ≥ 5 都凑不出来。 ## 面经里怎么考的 @@ -9,68 +27,170 @@ ## 思路 -先把人分成四类：两种都会（B）、只会技能 1（A）、只会技能 2（C）、都不会（这类永远不选）。每一类按费用从小到大排序，算前缀和 `PA`、`PB`、`PC`。 +### 1. 把人分成三类，再看成「单位」 -固定 K 后，假设从 B 里选 b 个（选 B 里最便宜的 b 个），那么还差 K − b 个会技能 1 的人和 K − b 个会技能 2 的人，各自从 A、C 里选最便宜的。费用是： +先按会什么把人分类：两种都会的记作 B 类，只会技能 1 的记作 A 类，只会技能 2 的记作 C 类。两种都不会的人选了只加费用、不加人数，永远不选。 -`f(b) = PB[b] + PA[K − b] + PC[K − b]` +再看「会技能 1 的人数」和「会技能 2 的人数」这两个计数。选一个 B 类的人，两个计数各加 1。选一个 A 类的人只加第一个计数，它要等到配上一个 C 类的人，两个计数才各加 1。所以把「能让两个计数各加 1 的最小组合」叫作一个**单位**，单位有两种： -b 的范围：不能超过 `len(B)`，也不能超过 K（多选 B 没用）；同时 `K − b` 不能超过 `min(len(A), len(C))`。范围是空的就填 -1。 +- 一个 B 类的人，费用就是他的费用。 +- 一个 A 类的人配一个 C 类的人，费用是两人之和。 -直接对每个 K 枚举 b 是 O(n²)。可以更快的原因是 **f 是凸函数**：数组升序时，前缀和每多加一项增加得越来越多，所以 `PB[b]` 是凸的；`PA[K − b]` 和 `PC[K − b]` 是凸函数换了方向，也还是凸的；凸函数相加仍然凸。凸函数在整数上可以二分找最低点（比较 `f(mid)` 和 `f(mid + 1)`），每个 K 是 O(log n)。 +要凑够 K，就是挑 K 个单位，让总费用最小。 + +> [!say] I split people into three groups: both skills, only skill one, only skill two. Picking one person with both skills, or one person from each single-skill group, raises both counts by exactly one, so I treat each of those as one unit and pick the K cheapest units. + +### 2. A 和 C 怎么配对 + +A 类按费用从小到大排序，C 类也排序，第 i 便宜的 A 配第 i 便宜的 C，得到一串「配对费用」。这样配是对的，原因如下。 + +在费用都不为负的前提下，多选的人只会让费用变大，所以最优方案里从 B 类选的人数 b 不超过 K，还差的 K − b 个会技能 1 的和 K − b 个会技能 2 的，分别从 A、C 里各补恰好 K − b 个。两边补的人互不影响，所以各自挑最便宜的 K − b 个，费用是 A 的前 K − b 小之和加上 C 的前 K − b 小之和。把这两个和按下标拆开重排，正好是前 K − b 个配对费用之和。 + +配对费用这一串本身也是从小到大的：A 和 C 都排好序了，第 i + 1 对的两个人都不比第 i 对的便宜。A、C 人数不一样多时，多出来的人配不成对，对凑 K 没用。Python 的 `zip` 在较短的一边用完时就停，正好把他们丢掉。 + +### 3. 挑 K 个最便宜的单位 + +把 B 类每个人的费用和每个配对费用放进同一个列表，排序，前 K 个之和就是 K 的答案。 + +这一步对的理由：B 类费用排好序是一串，配对费用是另一串，两串都是从小到大。从两串的并集里挑 K 个最小的，挑出来的在每一串里都是开头的一段（某串里挑了第 j 个却没挑第 j − 1 个，把它换成第 j − 1 个不会更贵）。假设在 B 那串里挑了开头 b 个，在配对那串里就挑了开头 K − b 个，这正好是第 2 节说的「从 B 选 b 个」的最优费用。并集里最小的 K 个，比任何一种 b 的选法都不贵，所以它就是所有 b 里的最小值。 + +单位一共有 `len(B) + min(len(A), len(C))` 个，K 超过这个数就是 -1。K 从 1 涨到 n，前 K 个之和每次只多加一项，用一个变量累加就行。 + +> [!say] The pair costs come out sorted, because the i-th cheapest skill-one person is paired with the i-th cheapest skill-two person. I merge them with the both-skill costs, sort once, and the answer for K is the prefix sum of the first K units, or minus one when there are fewer than K units. + +按单个人的费用贪心是错的，单位才是贪心的对象。在 `[(B, 3), (A, 1), (C, 5)]` 上，K = 1 时，「每次挑最便宜、还能帮上忙的人」会先挑 A 类的 1，接着还缺会技能 2 的人，C 类的 5 比 B 类的 3 贵，于是再挑 B 类的 3，共 4。直接只挑 B 类那个人就是 3。 + +> [!optional] 另一种做法：凸函数上二分。这是原来正文的主解，结果和上面一样，多一个 log。面试官顺着「固定 b」这条线往下问时用得上。 +> +> 三类各自排序，算前缀和 `PA`、`PB`、`PC`（`PA[t]` 是 A 类最便宜的 t 个之和）。固定 K，从 B 选 b 个时费用是 +> +> `f(b) = PB[b] + PA[K − b] + PC[K − b]` +> +> b 的范围：上界是 `min(K, len(B))`（B 选多于 K 个没用），下界是 `K − min(len(A), len(C))`（A、C 最多补这么多），再和 0 取大。范围为空就填 -1。 +> +> 对每个 K 枚举 b 是 O(n²)。f 是凸函数，意思是 f(b + 1) − f(b) 随 b 增大不变小： +> +> - `PB[b + 1] − PB[b]` 是 B 里第 b + 1 便宜的费用，b 越大越贵。 +> - `PA[K − b − 1] − PA[K − b]` 是 A 里第 K − b 便宜的费用取负。b 越大，K − b 越小，那个费用越便宜，取负后越大。`PC` 同理。 +> +> 三项的差分都不减，加起来也不减。所以 `f(mid) <= f(mid + 1)` 成立的 mid 是一段后缀，二分找这段的起点，就是最低点，每个 K 是 O(log n)。 +> +> ```python +> def min_cost_all_k(people): +> """people: [(技能集合, 费用)]，返回 K = 1..n 的答案""" +> A, B, C = [], [], [] +> for skills, cost in people: +> if 1 in skills and 2 in skills: +> B.append(cost) +> elif 1 in skills: +> A.append(cost) +> elif 2 in skills: +> C.append(cost) +> +> def pref(arr): +> arr.sort() +> p = [0] +> for v in arr: +> p.append(p[-1] + v) +> return p +> +> PA, PB, PC = pref(A), pref(B), pref(C) +> m = min(len(A), len(C)) +> res = [] +> for K in range(1, len(people) + 1): +> lo, hi = max(0, K - m), min(K, len(B)) +> if lo > hi: +> res.append(-1) +> continue +> f = lambda b: PB[b] + PA[K - b] + PC[K - b] +> l, r = lo, hi +> while l < r: # 凸函数二分找最低点 +> mid = (l + r) // 2 +> if f(mid) <= f(mid + 1): +> r = mid +> else: +> l = mid + 1 +> res.append(f(l)) +> return res +> ``` +> +> 2026-10-26 在云端用 Python 3.13.17 把这段代码和枚举所有子集的暴力解对拍，6300 组随机输入（种子 20261026，n 为 0 到 11）全部一致，输入怎么构造见「代码」一节的实测表。 +> +> 原正文给这个做法的英文讲法（原句的分号拆成了两句）：For a fixed K, if I take the b cheapest people who have both skills, I need K minus b from each single-skill group, so the cost is a sum of three prefix sums. That function is convex in b, so I can binary search its minimum instead of scanning every b. +> +> 下界最容易漏。把 `lo` 写成 0，在 `[(B, 5), (B, 6), (A, 1), (C, 1)]` 上，K = 2 时二分会试 b = 0，要读 `PA[2]`，而 A 类只有 1 个人，抛 `IndexError`。第 3 节的写法里没有这个下标，`zip` 和「单位个数」已经把范围管住了。 ## 代码 ```python -def min_cost_all_k(people): - """people: [(技能集合, 费用)]，返回 K = 1..n 的答案""" - A, B, C = [], [], [] +from typing import List, Set, Tuple + +Person = Tuple[Set[int], int] + +NO_TEAM = -1 + + +def min_cost_for_every_k(people: List[Person]) -> List[int]: + """people[i] = (这个人会的技能集合, 费用)，技能编号是 1 和 2，费用不为负。 + + 返回长度为 n 的列表，第 K-1 项是「至少 K 人会技能 1、至少 K 人会技能 2」 + 的最小总费用，凑不出来就是 -1。 + """ + both, only_skill1, only_skill2 = _split_by_skills(people) + units = sorted(both + _cheapest_pairs(only_skill1, only_skill2)) + + answers = [] + running_cost = 0 + for k in range(1, len(people) + 1): + if k <= len(units): + running_cost += units[k - 1] + answers.append(running_cost) + else: + answers.append(NO_TEAM) + return answers + + +def _split_by_skills(people: List[Person]) -> Tuple[List[int], List[int], List[int]]: + both, only_skill1, only_skill2 = [], [], [] for skills, cost in people: if 1 in skills and 2 in skills: - B.append(cost) + both.append(cost) elif 1 in skills: - A.append(cost) + only_skill1.append(cost) elif 2 in skills: - C.append(cost) + only_skill2.append(cost) + # 两种技能都不会的人对凑够 K 没有帮助，不选 + return both, only_skill1, only_skill2 - def pref(arr): - arr.sort() - p = [0] - for v in arr: - p.append(p[-1] + v) - return p - PA, PB, PC = pref(A), pref(B), pref(C) - m = min(len(A), len(C)) - res = [] - for K in range(1, len(people) + 1): - lo, hi = max(0, K - m), min(K, len(B)) - if lo > hi: - res.append(-1) - continue - f = lambda b: PB[b] + PA[K - b] + PC[K - b] - l, r = lo, hi - while l < r: # 凸函数二分找最低点 - mid = (l + r) // 2 - if f(mid) <= f(mid + 1): - r = mid - else: - l = mid + 1 - res.append(f(l)) - return res +def _cheapest_pairs(only_skill1: List[int], only_skill2: List[int]) -> List[int]: + """第 i 便宜的「只会技能 1」配第 i 便宜的「只会技能 2」，返回每对的费用。 + + zip 在较短的一边用完时停下，配不成对的人自然被丢掉。 + """ + return [c1 + c2 for c1, c2 in zip(sorted(only_skill1), sorted(only_skill2))] ``` -本机和枚举所有子集的暴力解随机对拍过 300 组（n ≤ 8）。 +空输入返回空列表，没有人会技能时全是 -1，都不用单独判断。Python 的 `int` 不会溢出，换成 Java、C++ 时累加要用 64 位整数。真实题目的输入格式（两个数组还是一个列表，技能怎么编码）未核实，交卷前按题面改 `_split_by_skills` 一处就行。 + +2026-10-26 在云端用 Python 3.13 跑了上面这段代码，和原做法（第 3 节后的可选知识框）、两个错误版本、枚举所有子集的暴力解放在一起比。按人贪心是第 3 节末尾描述的做法，对每个 K 从头选。漏下界的版本是原做法把 `lo` 写成 0： + +| 输入 | 测的是什么 | 结果 | +| --- | --- | --- | +| 「题目」里的 7 人例子 | 题面例子 | 正解、原做法、暴力都是 `[3, 8, 15, 28, -1, -1, -1]`，按人贪心是 `[3, 12, 19, 28, -1, -1, -1]` | +| `[(B, 3), (A, 1), (C, 5)]` | 按人贪心的反例 | 正解和暴力 `[3, 9, -1]`，按人贪心 `[4, 9, -1]` | +| `[(B, 5), (B, 6), (A, 1), (C, 1)]` | 原做法漏掉下界 | 正解和原做法 `[2, 7, 13, -1]`，漏下界的版本抛 `IndexError` | +| 空列表、全都不会、只有 A 类、一个 B 类、费用全 0、费用 10^18 | 边界 | 正解、原做法、暴力三者一致 | +| 6300 组随机输入（种子 20261026，n 为 0 到 11）。人的类别分 7 种取法：四类都有、缺 B、缺 A、缺 C、没有都不会的、只有 B 和都不会、只有 A 和 C。费用分 3 种取法：0 到 20、大多相同（3 或 5）、0 或 1 | 对拍，含某类为 0 个、费用相同、K 取到最大可能值、凑不出来 | 正解和原做法都与暴力 0 处不一致。按人贪心错 1296 组，漏下界的版本 5776 组抛 `IndexError`。每组都核对了 K 不超过单位个数时有解、超过时暴力也是 -1 | +| n = 200000 随机输入（种子 1，费用 0 到 10^9） | 两种做法一致、计时 | 结果相同。跑了两次，正解 69 到 90 毫秒，原做法 517 到 633 毫秒 | ## 复杂度 -排序 O(n log n)，所有 K 合计 O(n log n)。 +- 第 3 节的正解：排序 O(n log n)，之后一遍 O(n)，额外空间 O(n)。 +- 可选知识框里的原做法：排序 O(n log n)，每个 K 二分 O(log n)，合计也是 O(n log n)。 ## 易错点 -- 题目是「至少 K 个」：B 类的人一个人同时满足两边，所以要和 A、C 一起权衡，不能贪心地先选最便宜的人。 -- 都不会的人不选。 -- 范围的下界 `K − min(len(A), len(C))` 容易漏，漏了会越界或给出不合法的方案。 - -## 英文讲法 - -> [!say] For a fixed K, if I take the b cheapest people who have both skills, I need K minus b from each single-skill group, so the cost is a sum of three prefix sums; that function is convex in b, so I can binary search its minimum instead of scanning every b. +- 按单个人的费用贪心会错，`[(B, 3), (A, 1), (C, 5)]` 的 K = 1 得到 4 而不是 3，贪心的对象要换成单位，见思路第 3 节。 +- A、C 配对前要各自排序，第 i 便宜配第 i 便宜，见思路第 2 节。 +- 两种技能都不会的人只加费用，不选，见思路第 1 节。 +- 用原来的二分写法时，b 的下界 `K − min(len(A), len(C))` 漏掉会越界，见思路第 3 节后的可选知识框。
meta
@@ -1 +1,5 @@ -{} +{ + "depth_guide": "2026-10-23", + "rewritten_by": "cloud:20261026-1620", + "rewritten_at": "2026-10-27" +}