题意
静态哈夫曼编码是一种主要用于文本压缩的编码算法。给定一个由 \(N\) 个不同字符组成的特定长度的文本，算法选择 \(N\) 个编码，每个不同的字符一个编码。使用这些编码压缩文本，当选择编码算法构建一个具有 \(N\) 个叶子的二叉树时，对于 \(N \ge 2\)，树的构建如下：
-
对文本中的每个不同字符，构建一个仅包含单个结点的树，并为其分配权值，权值与文本中该字符出现的次数一致。
-
构建一个包含上述 \(N\) 棵树的集合 \(s\)。
-
当 \(s\) 包含多于一棵树时：
（a） 选择最小的权值 \(t_1\in s\)，并将其从 \(s\) 中删除；
（b） 选择最小的权值 \(t_2 \in s\)，并将其从 \(s\) 中删除；
（c） 构建一棵新树 \(t\)，\(t_1\)为其左子树，\(t_2\) 为其右子树，并且 \(t\) 的权值为 \(t_1, t_2\) 权值之和；
（d） 将 \(t\) 加入 \(s\) 集合。
-
返回保留在 \(s\) 中的唯一一棵树。
对于文本 "abracadabra"，由上述过程生成的树，可以像下图左侧，其中每个内部结点编辑有子树根的权值。请注意获得的树也可以像下图右侧或其它，因为在步骤 3(a), 3(b) 中，结合可能包含几个权值最小的树。
对文本中的每个不同字符，其编码取决于最终树中从根到对应字符的叶子之间的路径，编码的长度是这条路径中的边数（与路径中的内部结点一致）。假设该算法构建的是左侧的树，"r" 的代码长度为 \(3\)，"d" 的代码长度为 \(4\)。
根据算法选择的 \(N\) 个代码的长度，找所有字符总数的最小值。
输入格式
输入文件包含多个测试用例，每个测试用例如下所述：
第一行包含一个整数 \(N\)（\(2 \le N \le 50\)），表示文本中出现的不同字符数。
第二行包含 \(N\) 个整数 \(Li\)（\(1 \le Li \le 50\)，\(i=1,2,...,N\)）,表示由 Huffman 算法生成的不同字符的编码长度。
假设至少存在一棵上述算法构建的树，可以生成具有给定长度的编码。
输出格式
对每个测试用例，输出一行，表示所有字符总数的最小值。
\(Code\)
这个不是简单的求哈夫曼编码，而是反其道而行之，提供了各个字符哈夫曼编码的长度，求文章总字符个数最少是多少个。
我们同样从最底层开始考虑（假设是 $ m $），显然最底层的字符最少出现次数是 $ 1 $。那么 $ m-1 $ 层叶子节点的最小值应该是第 $ m $ 层的最大值。同时 $ m-1 $ 层应该还有一些非叶子节点是有第 $ m $ 层的节点两两合并而来。
我们一层层模拟这个过程即可，用 \(deep_i\) 保存第 \(i\) 层的节点，初始输入中给的叶子全部为 \(0\)。
最后根节点的值就是文章的最小总字符数。
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
using namespace std;
typedef long long ll;
const int maxn=55;
int n,d[maxn],maxd;
vector<ll> deep[maxn];
ll ans,temp;
int main (){
while(scanf("%d",&n)!=EOF){
//清空
ans=temp=maxd=0;
for(int i=0;i<=n;i++)deep[i].clear();
//输入
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
d[x]++;
deep[x].push_back(0);
maxd=max(maxd,x);
}
//从最下面一层往上计算
temp=1;
for(int i=maxd;i>=1;i--){
for(int j=0;j<SZ(deep[i]);j++){
if(deep[i][j]==0){
deep[i][j]=temp;
}
}
sort(deep[i].begin(),deep[i].end());
for(int j=0;j<SZ(deep[i]);j+=2){
deep[i-1].push_back(deep[i][j] + deep[i][j+1]);
}
temp=deep[i][SZ(deep[i])-1];
}
//输出根节点，即总字符数
cout<<deep[0][0]<<endl;
}
return 0;
}