题目重点：按活跃候选人重算每张选票的最高偏好，明确有效票、平局和不完整偏好表的规则。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版每张票给互不重复的候选排序，可不列全候选；每轮取仍活跃的首个偏好。无可用偏好的票成为 exhausted，不计当轮有效票。
- 每轮只淘汰一个最低票候选；最低票平局时按候选名字典序淘汰，以便输出确定。此规则仅为训练假设，不能称为原面试规定。严格超过当轮有效票 50% 才胜；只剩一人时直接返回。
解题路线
- 维护 active 候选集合；每一轮遍历所有 ballots，从左到右找第一个仍 active 的名字并计票。这样自然处理前几偏好已被淘汰的转票，而不是只看被淘汰者的原第一偏好。
- 计算 valid_votes（排除 exhausted），检查票数×2>valid_votes。若无人过半，找最少票候选，按明确 tie-break 淘汰并重复。
- 投票阶段的单调性是 active 每轮少一个，至多 C 轮终止。若票量很大，可为每张票保留当前偏好指针，仅在所属候选被淘汰时推进，减少重复扫描；但还需正确处理 exhausted 和平局。
手动走一遍
题目 A、A、B、B、C 五张票，首轮 A=2、B=2、C=1；淘汰 C，其选票下一有效偏好为 B，第二轮 B=3、A=2，B 严格过半。若一张票只写 C，淘汰后它 exhausted，第二轮分母变 4。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import Counter
def instant_runoff(ballots: list[list[str]]) -> str | None:
"""Training contract: eliminate one least-vote candidate, lexical tie break."""
if not ballots:
return None
candidates = set()
for ballot in ballots:
if len(ballot) != len(set(ballot)):
raise ValueError("duplicate preference")
candidates.update(ballot)
active = candidates.copy()
while active:
votes = Counter()
for ballot in ballots:
choice = next((name for name in ballot if name in active), None)
if choice is not None:
votes[choice] += 1
valid_votes = sum(votes.values())
for name in active:
if votes[name] * 2 > valid_votes:
return name
if len(active) == 1:
return next(iter(active))
# Source does not specify the tie rule. This is a deterministic exercise.
loser = min(active, key=lambda name: (votes[name], name))
active.remove(loser)
return None
复杂度
C 个候选、V 张票、每张最长 P 个偏好：直接重算每轮最多 C 轮，O(CVP) 时间，O(C) 计票及 active 空间（不计输入）。指针优化可把全部转票扫描压到 O(VP)，每轮仍需 O(C) 统计/找最低。
易错点与追问
容易失分的边界
- 淘汰后只转原来投给被淘汰者的票，却不重新检查其他 exhausted 状态。
- 票数分母始终用最初总票数，忘了可能 exhausted。
- 把恰好 50% 当‘超过’。
- 最低票平局时悄悄按容器遍历顺序淘汰。
- 同一张选票重复列候选导致重复偏好不清。
继续深挖
- 最低票两人并列时同时淘汰还是按规则选一个？
- 不完整排序和 exhausted ballots 如何计分母？
- 百万张选票如何流式计数和复算？
- 如何给每轮结果留下可审计记录？
