有 种不同的单词，从 到 进行编号。其中第 种单词出现的总次数为 。要用 进制串 来替换第 种单词，满足对于任意的 ，都有： 不是 的前缀。
- 替换以后得到的新的长度最小为多少；
- 在确保总长度最小的情况下，最长的 的最短长度是多少？
链接
题解
考虑当 时，其最优化条件相当于哈夫曼树，即：将所有单词作为一棵树放在集合中，每次取出两个最小的合并起来，放回集合，直到集合中只剩下一个元素。
显然， 时，将「两个最小的」换成「 个」即可。
考虑第二个条件，使最长的 最短。在哈夫曼树算法中 的长度体现在一个节点被合并的次数上，只需要将每一个节点被合并的次数作为第二关键字即可。
最后一个问题，如果每次取出 个，加入 个，最后不够 个怎么办。考虑到每次减少了 个，需要将 个减掉 —— 只需加入一些空节点（）使 即可。
代码
#include <cstdio>
#include <queue>
#include <utility>
const int MAXN = 100000;
const int MAXK = 9;
int main() {
int n, k;
scanf("%d %d", &n, &k);
std::priority_queue< std::pair<long long, int>, std::vector< std::pair<long long, int> >, std::greater< std::pair<long long, int> > > q;
for (int i = 0; i < n; i++) {
long long x;
scanf("%lld", &x);
q.push(std::make_pair(x, 0));
}
while ((q.size() - 1) % (k - 1) != 0) q.push(std::make_pair(0, 0));
long long ans = 0;
while (q.size() > 1) {
std::pair<long long, int> newNode;
for (int i = 0; i < k; i++) {
std::pair<long long, int> p = q.top();
q.pop();
ans += p.first;
newNode.first += p.first;
newNode.second = std::max(newNode.second, p.second);
}
newNode.second++;
q.push(newNode);
}
std::pair<long long, int> p = q.top();
printf("%lld\n%d\n", ans, p.second);
return 0;
}