QOJ.ac

QOJ

Límite de tiempo: 5 s Límite de memoria: 1024 MB Puntuación total: 100

#4969. RCV 简化

Estadísticas

以下内容摘自 Ballotpedia [ https://ballotpedia.org/Ranked-choice_voting_(RCV) ]:

概括地说,排序选择投票(ranked-choice voting)流程在单人胜出选举中按以下方式进行:

  1. 选民在选票上按偏好对候选人进行排序。
  2. 如果某位候选人获得了超过半数的首选票(即 50% 加 1 票),则该候选人直接获胜。
  3. 反之,如果没有候选人获得超过半数的首选票,则首选票数最少的候选人将被淘汰。
  4. 所有投给被淘汰候选人的首选票将被作废,并转而计入这些选票上标注的第二偏好候选人。
  5. 重新统计票数,以确定是否有候选人获得了调整后选民的多数票。
  6. 重复此过程,直到有候选人获得多数票为止。

示例:假设选举中有四名候选人。下表展示了每位候选人获得的原始首选票总数:

候选人 首选票数 百分比
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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.