以下内容摘自 Ballotpedia [ https://ballotpedia.org/Ranked-choice_voting_(RCV) ]:
概括地说,排序选择投票(ranked-choice voting)流程在单人胜出选举中按以下方式进行:
- 选民在选票上按偏好对候选人进行排序。
- 如果某位候选人获得了超过半数的首选票(即 50% 加 1 票),则该候选人直接获胜。
- 反之,如果没有候选人获得超过半数的首选票,则首选票数最少的候选人将被淘汰。
- 所有投给被淘汰候选人的首选票将被作废,并转而计入这些选票上标注的第二偏好候选人。
- 重新统计票数,以确定是否有候选人获得了调整后选民的多数票。
- 重复此过程,直到有候选人获得多数票为止。
示例:假设选举中有四名候选人。下表展示了每位候选人获得的原始首选票总数:
| 候选人 | 首选票数 | 百分比 |
|---|---|---|
| Candidate A | 475 | 46.34% |
| Candidate B | 300 | 29.27% |
| Candidate C | 175 | 17.07% |
| Candidate D | 75 | 7.32% |
在上述场景中,没有候选人获得超过半数的首选票。因此,首选票数最少的候选人(Candidate D)被淘汰。将那些以 Candidate D 为首选的选票进行调整,转而计入其第二偏好候选人。假设在 Candidate D 的 75 张首选票中,有 50 张将 Candidate A 列为第二偏好,25 张将 Candidate B 列为第二偏好。调整后的票数统计如下:
| 候选人 | 调整后的首选票数 | 百分比 |
|---|---|---|
| Candidate A | 525 | 51.22% |
| Candidate B | 325 | 31.71% |
| Candidate C | 175 | 17.07% |
在第二轮统计中,Candidate A 获得了 51.22% 的选票,从而赢得了选举。
说明: 如果多名候选人的首选票数并列最少,则所有这些候选人都会被淘汰。因此,未被淘汰的候选人其首选票数必须至少比被淘汰的候选人多一票。
题目描述
我们已经收到了每位候选人获得首选票的百分比信息,但我们不知道候选人是如何被列为第二、第三偏好等的。请编写一个程序来移除那些不可能获胜的候选人。更具体地说,给定一组候选人的当前票数,找出所有不可能获胜的候选人。
输入格式
第一行包含一个整数 $N$ ($1 \le N \le 100,000$),表示选票总数。接下来的 $N$ 行,每行包含一个候选人的名字,表示该选民的首选票投给了谁。每个候选人的名字由 1-25 个字母(大小写)组成,从第一列开始。
输出格式
第一行输出一个正整数 $C$,表示不可能获胜的候选人数量。接下来的 $C$ 行,每行包含一个不可能获胜的候选人名字。候选人名字应按字典序(升序)排列。
样例
样例输入 1
5 Alice Alice Bob Bob Carol
样例输出 1
1 Carol
样例输入 2
2 Alice Bob
样例输出 2
2 Alice Bob