[Java] UVa 10954 Add All

題目連結

題意:
每組測資給若干數字求總和，每次任兩數相加，直到最後。
過程中產生的和會形成cost

例如:
1+2=3 (cost 3)

若有 1, 2, 3 三數

選擇 1+2，再+3，則是
1+2 = 3 (cost 3)
3+3 = 6 (cost 6)
總cost為 9

也可以先2+3再+1
2+3 = 5 (cost 5)
5+1 = 6 (cost 6)
總cost為 11

題目要求輸出最小的 cost

解法:
上例中，最早進行計算的會產生最多次 cost
因此，要從最小的數開始
每次加完後也會成為下次可能相加的元素

做法是每次抓出最小的兩數相加
計算 cost 並將結果放回去，可以得到最小的總 cost

我們選用 PriorityQueue 資料結構，放進去的數字會自行 sort(由小到大)
放進去是 add 方法，取出是 poll 方法，每次 poll 會得到最小的值

程式(Java):