【CS50x】Runoff 题解（上）

前言

CS50x 是哈佛大学推出的一门知名公开课，本课程是一门计算机科学的导论课程，适合于对计算机科学感兴趣的任何人学习，不需要任何基础。通过学习本课程有助于对计算机科学的体系建立一个基本的概念，其学习内容如下：

Runoff

昨天我们更新了【CS50x】Plurality 题解，Plurality 是我们平时最常使用的投票排名系统，也被称为“得票最多者当选”或者”赢家通吃“的方法，就是每个选民只能投票给一个候选人，在选举结束时，获得最多选票的候选人会成为选举的胜利者。

但这种方法局限性非常大，就比如下面这种三个候选人的情况怎么选：

Alice 和 Bob 各有两张选票，我们难道要宣布两个赢家吗？所以就牵扯到今天我们要使用的 Runoff 投票系统，在该系统中，选民可以投票给多个候选人，可以根据喜欢偏好来对候选人进行排名，而不是仅仅投票给他们最喜欢的候选人，由此产生的选票如下所示：

这样做会使以前平分秋色的选举可能产生一个赢家，Alice 和 Bob 刚开始票数相同，Charlie 出局，发现选择 Charlie 的投票者更喜欢 Alice，所以可以宣布获胜者为 Alice。

但是还有一种情况：

这种情况下，Charlie 4票，Bob 3票，Alice 2票，但是上面五个人都是喜欢 Alice，Bob 大于 Charlie，所以我们必须加上一条规则：只有候选人获得超过50%的选票才可以获得胜利，如果没有人超过50%，就发生“即时决选”，将得票最少的候选人淘汰出局，原先原先选择该候选人作为第一选择的任何人现在都将考虑他们的第二选择。

如果没有一个候选人获得多数选票，那么最后一个候选人就会被淘汰，任何投票给他们的人都会转而投票给他们的下一个候选人(如果还没有被淘汰)。一旦一个候选人获得多数票，那个候选人就被宣布为胜利者。

但是如果剩下的候选人拥有一样的票数，那么意味着我们需要淘汰所有人，所以我们必须考虑这个边界情况。

总结

• 读取候选人信息
• 得到未淘汰的候选人的票数，总结为偏好数组
• 判断是否有胜者产生
• 找到最小值
• 判断是否为平局
• 淘汰票数最少的候选人