[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):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNext()) {
	int N = sc.nextInt();
	if (N == 0)
	break;
	PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
	while (N-- > 0)
	pq.add(sc.nextInt());
	int ans = 0;
	while (pq.size() >= 2) {
	int a = pq.poll();
	int b = pq.poll();
	int sum = a + b;
	ans += sum;
	pq.add(sum);
	}
	System.out.println(ans);
	}
	}
	}

view raw UVa10954.java hosted with ❤ by GitHub