链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1895
题意：
有n（n≤5000）个数的集合S，每次可以从S中删除两个数，然后把它们的和放回集合，直到剩下一个数。
每次操作的开销等于删除的两个数之和，求最小总开销。所有数均小于1e5。
分析：
用一个优先队列代表集合S，每次从中取出两个最小的数相加，再把这两个数的和放回S中即可。
与 Huffman 编码的建立过程类似。
代码：
1 #include <cstdio> 2 #include <queue> 3 using namespace std; 4 5 int main(){ 6 int n; 7 while(scanf("%d", &n) && n){ 8 priority_queue<int, vector<int>, greater<int> > Q; 9 for(int x, i = 0; i < n; i++){ 10 scanf("%d", &x); 11 Q.push(x); 12 } 13 int ans = 0; 14 while(Q.size() > 1){ 15 int a = Q.top(); Q.pop(); 16 int b = Q.top(); Q.pop(); 17 ans += a + b; 18 Q.push(a + b); 19 } 20 printf("%d\n", ans); 21 } 22 return 0; 23 }