【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d221
【解題想法】Greedy【筆記】
- 因為加法的代價會不斷累計，因此不斷地從最小的數字先相加，代價最低。
- 利用priority_queue，但排序由小到大。取出最小的兩個數字，相加後放回priority_queue，重新排序。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n, num, a, b;
while (cin >> n){
if (n == 0) break;
priority_queue <int, vector<int>, greater<int>> pq;
long long count = 0;
for (int i = 0; i < n; i++){
cin >> num;
pq.push(num);
}
for (int i = 0; i < n-1; i++){
a = pq.top();
pq.pop();
b = pq.top();
pq.pop();
count += a+b;
pq.push(a+b);
}
cout << count << endl;
}
}
while True:
try:
n = int(input())
if n == 0:
break
lst = list(map(int, input().split()))
lst.sort()
ans = 0
total = lst[0]
for i in range(n-1):
num = lst.pop(0) + lst.pop(0)
ans += num
lst.append(num)
lst.sort()
print(ans)
except:
break