这道题用哈夫曼树做，使用STL中的优先队列。
优先队列：
#include <queque> //升序 priority_queuqe <int,vector<int>,greater<int> > q; //在q前面需要空一格，否则就是右移. priority_queque <int,vector<int>,less<int> >q; //降序,也可不写，默认。 q.push(a) //将a压入栈 q.top() ;//取出栈顶元素 q.pop(); //栈顶指针减一。 q.size() ;//队列中有几个元素。
原理思想是：当一直在合并两个最小堆时消耗值最小，所以就是用哈夫曼树，因为一直是最小的，所以最后算的值也最小。
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 using namespace std; 5 //使用优先队列完成,使用到霍夫曼数 6 int n; 7 const int MAXN=10000; 8 int a[MAXN]; 9 int main() 10 { 11 priority_queue <int,vector<int>,greater<int> >q; //必须加上gteater<int> 12 scanf("%d",&n); 13 int sum=0; 14 for(int i=0; i<n; i++) 15 { 16 scanf("%d",&a[i]); 17 q.push(a[i]); 18 } 19 while(q.size()>1) 20 { 21 int a=q.top(); 22 q.pop(); 23 int b=q.top(); 24 q.pop(); 25 q.push(a+b); 26 sum+=(a+b); 27 28 } 29 printf("%d",sum); 30 return 0; 31 }
我的错误：
1.忘了优先队列默认是从大到小的，一直在算最大值。
原文：https://www.cnblogs.com/yangln/p/11828573.html