题意：给定哈夫曼树的n个叶子节点距离根的距离，求文本至少需要多少个字符可以建出这样的哈夫曼树
思路：策略：对于第i层的叶子节点，，赋值为i+1层的节点中权值最大的点这种情况下字符数最少。详见代码：
/********************************************************* file name: LA6533.cpp author : kereo create time: 2015年02月07日 星期六 22时05分45秒*********************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>#include<map>#include<vector>#include<stack>#include<cmath>#include<string>#include<algorithm>using namespace std;typedef long long ll;const int sigma_size=26;const int N=100+50;const int MAXN=100000+50;const int inf=0x3fffffff;const double eps=1e-8;const int mod=1000000000+7;#define L(x) (x<<1)#define R(x) (x<<1|1)#define PII pair<int, int>#define mk(x,y) make_pair((x),(y))int n;ll step;int a[N];priority_queue<ll>Q1,Q2;void init(){while(!Q1.empty())Q1.pop();while(!Q2.empty())Q2.pop();step=1;memset(a,0,sizeof(a));}int main(){while(~scanf("%d",&n)){init();for(int i=1;i<=n;i++){int x;scanf("%d",&x);a[x]++;}ll ans=0;for(int i=50;i>=1;i–){if(a[i]){while(a[i]){Q1.push(step);ans+=step;a[i]–;}}while(Q1.size()>1){step=max(step,Q1.top());ll tmp=Q1.top(); Q1.pop(); //要long longstep=max(step,Q1.top());tmp+=Q1.top(); Q1.pop();Q2.push(tmp);}if(Q1.size())step=max(step,Q1.top());while(Q2.size()){Q1.push(Q2.top());Q2.pop();}}printf("%lld\n",ans);}return 0;}
真正的爱，应该超越生命的长度心灵的宽度灵魂的深度
