静态霍夫曼编码是一种主要用于文本压缩的编码算法。给出的文本为 由N个不同字符组成的特定大小，算法选择N个代码，每个代码对应一个不同的字符 性格使用这些代码压缩文本。为了选择代码，算法构建一个 有N片叶子的二元根树。对于N≥2，树可按如下方式构建。 1.对于文本中的每个不同字符，构建一个仅包含单个节点的树，并将其分配给它 与文本中字符出现次数一致的权重。 2.建立一个包含上述N棵树的集合。 3.当s包含多个树时： （a） 选择具有最小权重的t1∈s，并将其从s中删除。 （b） 选择具有最小权重的t2∈s，并将其从s中删除。 （c） 构建一个新的树t，t1作为其左子树，t2作为其右子树，并将 t1和t2的权重之和。 （d） 将t包含在s中。 4.返回s中唯一保留的树。 对于文本“abracabra”，通过上述过程生成的树可以看起来像 下图左侧，其中每个内部节点都标有子树根的权重 在该节点处。注意，获得的树也可以看起来像图片右侧的树，其中 因为在步骤3a和3b，集合s可以包含具有最小权重的若干树。 对于文本中的每个不同字符，其代码取决于最终树中存在的路径， 从根到对应于字符的叶。代码的长度是边的数量 这与路径中的内部节点的数量一致）。假设树打开 左边是由算法构建的，“r”的代码长度为3，而“d”的代码的长度为4。 您的任务是，给定算法选择的N个代码的长度，找到最小大小（总计 字符数），以便生成的代码具有N个长度。
输入 输入文件包含几个测试用例，每个测试用例如下所述。 第一行包含表示不同字符数的整数N（2≤N≤50） 出现在文本中的。第二行包含N个整数Li 指示代码的长度 通过霍夫曼算法为不同字符选择（i＝1，2，…，N时，1≤Li≤50）。你可以 假设至少有一棵树，按照所述构建，生成具有给定长度的代码。 输出 对于每个测试用例，输出一行，其中一个整数表示最小大小（ 字符），以便生成的代码具有给定的长度。
样本输入 2. 1 1 4. 2 2 2 2 10 8 2 4 7 5 1 6 9 3 9 样本输出 2. 4. 89
思路
输入数据的同时，求树的最大深度d，即最长编码长度。根据输入的编码长度，在对应的层插入权值为0的节点。从树的最大深度处，即最底层开始，向上推导。
lastMax为下一层权值最大节点的权值，由于最底层没有下一层，而最底层的权值只能为1，所以最底层的lastMax记为1。
该层未知权值的节点，在初始化时权值被设置为0，该层所有节点权值的最小值为下一层权值最大节点的权值，所以将权值为0的节点的权值全部设置为lastMax。将该层用sort排序，每两个节点合并后插入上一层，该层权值最大的节点的权值赋值给lastMax。
到达树根后，输出树根的权值，即最小字符数。
AC代码
#include <iostream>
#include <vector>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;
int main()
{
int n, l;
int d;
vector<long long> v[60];
while (cin >> n)
{
d = 0;
for (int i = 0; i < n; i++)
{
v[i].clear();
}
for (int i = 0; i < n; i++)
{
cin >> l;
v[l].push_back(0);
d = max(d, l);
}
long long lasMax = 1;
for (int i = d; i > 0; i--)
{
for (int j = 0; j < v[i].size(); j++)
{
if (!v[i][j])
{
v[i][j] = lasMax;
}
}
sort(v[i].begin(), v[i].end());
for (int j = 0; j < v[i].size(); j += 2)
{
v[i - 1].push_back(v[i][j] + v[i][j + 1]);
}
lasMax = *(v[i].end() - 1);
}
cout << *(v[0].begin()) << endl;
}
return 0;
}