切換
舊版
前往
大廳
主題

ZeroJudge - e592: 10142 - Australian Voting 解題心得

Not In My Back Yard | 2020-01-06 23:06:16 | 巴幣 0 | 人氣 294

題目連結:


題目大意:
給定一正整數 T ,代表有 T 筆測試資料。

每筆測資開頭有一空白列。接著的一列給定一正整數 n (n ≦ 20),代表有 n 位候選人。接下來的 n 列輸入,每列給定一個字串(可能有空白字元),代表一位候選人的名字。再接續著有不定量列數的輸入,每列有 n 個正整數,代表其中一位選民心中對於候選人的排名(越左邊的排名越前面,且候選人依據給定的順序編號為 1 ~ n)。

在一次選舉之中,在全部的選民的第一順位(最左邊的數字)中佔比 50% 的候選人,則該候選人當選;如果沒有人超過 50% ,則將最低票數的人淘汰並從選民的志願序中移除,然後重複以上步驟直到有人超過 50% 或是所有人的佔比都相同。

請找出當選或是多位並列的候選人之名字。每組測資之間的輸出需要有一空白列。



範例輸入:
1

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2


範例輸出:
John Doe


解題思維:
先將所有資訊存起來,包含候選人姓名以及各個選民的候選人排名。然後照著題目所說,先統計每個候選人各自在各個選民的第一順位中的票數(佔有數),如果有人超過 50% 或是佔有數全部一樣的話,就輸出那些人。

如果當沒人超過或沒有全部並列,則將佔有最少的人淘汰(看是要從選民的排名陣列裡直接刪除還是用一個變數表示忽略此候選人)。然後就重複上面統計的步驟。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

心彩
錯字 痛計->統計
2023-06-15 12:02:30
Not In My Back Yard
感謝,已更正。
2023-06-15 19:12:57

相關創作

更多創作