題目： UVa - 10954 - Add All

題目說明

給一些數字，將數字全部相加，相加的過程需要成本，例如 1 + 3 = 4，則成本為 4，求將數字全部相加後的成本為何。

解題思路

每次選擇最小的兩者相加即可花費最少的成本。使用 Priority_queue，每次取兩個最小的數字出來相加即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <queue>

using namespace std;

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main()
{
    int n, tmp;
    priority_queue<int, vector<int>, greater<int>> pq;
    while (cin >> n && n)
    {
        int ret = 0;
        while (n--) cin >> tmp, pq.push(tmp);
        while (pq.size() > 1)
        {
            int n1 = pq.top(); pq.pop();
            n1 += pq.top(), pq.pop();
            ret += n1;
            pq.push(n1);
        }
        cout << ret << '\n';
        pq.pop();
    }
}