---
# System prepended metadata

title: '[競程] 澳洲選舉'
tags: [競程]

---

# [競程] 澳洲選舉

###### tags: `競程`

## 問題
* ZeroJudge: [e592](https://zerojudge.tw/ShowProblem?problemid=e592)

澳洲的選票要求選民按照選擇的順序對候選人進行排名。
* 最初僅計算選民的第一順位。如果一個候選人獲得超過50％的選票，則該候選人當選。如果沒有候選人獲得超過50％的選票，則所有票數最少的候選人將被淘汰。
* 如果在某張選票上的第一順位候選人被淘汰了，則將後面順位往前移動。

重複進行上述步驟直到一名候選人獲得超過50％的選票或所有候選人並列為止。所有候選人並列則不回傳任何名字。

給定候選人數量`n`、候選人名單 `candidates`和全部選票內容`ballots`，設計一個函式回傳最後當選者的名字。


## 範例
```python
輸入：n = 3
     candidates = ["Alice", "Bob", "Eve"]
     ballots = [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 2, 3], [3, 1, 2]]
輸出："Alice"
```
## 思路
* 因為有50%門檻的限制條件，所以得到最高票候選人不能直接回傳，必須使用一個`while`迴圈，只有滿足特定條件才跳出這個迴圈並回傳答案。
* 人名、選票總數、選票序號之間的關聯需謹慎對待。

## 解答
```python=
from numpy import argmax, argmin

def vote(n, candidates, ballots):
    threshold = int(len(ballots) / 2) # 超過這個票數就是過半

    while 1:
        if not candidates:
            return None
        stats = [0 for _ in range(n)]
        for b in ballots:
            for i in range(n):
                if b[i] == min(b):
                    stats[i] += 1
        if max(stats) > threshold:
            return candidates[argmax(stats)]
        else:
            minballot = min(stats)
            while candidates and min(stats) == minballot:
                loser = argmin(stats)
                stats.pop(loser)
                candidates.pop(loser)
                for b in ballots:
                    b.pop(loser)
                n -= 1
    
```

