切換
舊版
前往
大廳
主題

ZeroJudge - f168: m4a2-分配寶物(Treasure) 解題心得

Not In My Back Yard | 2020-08-14 00:00:14 | 巴幣 0 | 人氣 480

題目連結:


題目大意:
第一列給定一正整數 N (3 ≦ N ≦ 16),代表有 N 個寶物。接著一列給定 N 個正整數(皆小於 10 ^ 7),代表這 N 個寶物的價值。

試問,是否可以將這 N 個寶物分給三個人(每個寶物都要分給其中一個人)並使得每個人得到的寶物價值總和皆一致?



範例輸入:
範例輸入 1:
3
1 2 3

範例輸入 2:
4
1 2 3 3

範例輸入 3:
10
12 53 34 23 29 26 19 10 1 6


範例輸出:
範例輸出 1:
NO

範例輸出 2:
YES

範例輸出 3:
YES


解題思維:
直接窮舉出所有 3 ^ N 種的分配情況,也就是第一個寶物看要分給誰、第二個要給誰、……遞迴到最後一個寶物為止。然後如果有出現三個人的價值皆恰為總價值 ÷ 3 之值,則代表可以平分寶物的價值,輸出「YES」。

如果完全沒出現過以上的組合,則輸出「NO」。




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

創作回應

更多創作