uva10954 Add All

题目：

Yup!! The problem name reflects your task; just add a set of numbers. But you may feel yourselves
condescended, to write a C/C++ program just to add a set of numbers. Such a problem will simply
question your erudition. So, lets add some flavor of ingenuity to it.
Addition operation requires cost now, and the cost is the summation of those two to be added. So,
to add 1 and 10, you need a cost of 11. If you want to add 1, 2 and 3. There are several ways
1 + 2 = 3, cost = 3 1 + 3 = 4, cost = 4 2 + 3 = 5, cost = 5
3 + 3 = 6, cost = 6 2 + 4 = 6, cost = 6 1 + 5 = 6, cost = 6
Total = 9 Total = 10 Total = 11
I hope you have understood already your mission, to add a set of integers so that the cost is minimal.
Input
Each test case will start with a positive number, N (2 ≤ N ≤ 5000) followed by N positive integers
(all are less than 100000). Input is terminated by a case where the value of N is zero. This case should
not be processed.
Output
For each case print the minimum total cost of addition in a single line.
Sample Input
3
1 2 3
4
1 2 3 4
0
Sample Output
9
19

其实这道题的意思实际上就是霍夫曼编码。其实就是每次从集合中删除两个数，然后将它们的和放回集合，直到剩下一个数。每次操作的开销等于删除的两个数之和，求最小总开销。
要求最小总开销，只需要每次从集合中取出两个最小的数就可以，问题是集合在动态变化，因此需要每次维护集合中元素的大小关系，因为n比较小，可以采用优先队列。

参考代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 5000+10;

LL a[N];
vector<LL> v;
priority_queue<LL, vector<LL>, greater<LL> > que;

void init() {
    memset(a, 0, sizeof(a));
}

void input(const int n) {
    for (int i = 0;i < n;++i) {
        cin >> a[i];
        que.push(a[i]);
    }
}

LL cal(const int n) {
    v.clear();
    LL ans = 0;
    LL ans1 = 0;
    LL num1;
    LL num2;
    while (!que.empty() && que.size() >= 2) {
        num1 = que.top();
        que.pop();
        num2 = que.top();
        que.pop();
        ans1 = num1 + num2;
        //cout << "ans1 = " << ans1 << endl;
        v.push_back(ans1);
        que.push(ans1);
        ans1 = 0;
    }
    que.pop();
    for (auto it = v.begin();it != v.end();++it) {
        ans += *it;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    while (cin >> n) {
        if (n == 0) break;
        init();
        input(n);
        LL ans = cal(n);
        cout << ans << endl;
    }
    return 0;
}