题解 | #作弊#

先引用一段百度百科对哈夫曼树的介绍：

在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

据此我们可以知道，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码 可以使得我们对字符的编码的 字符串的平均长度、期望值降低。

事实上根据本题样例，手玩一下也能得到类似的结论：如果某个字符老是出现，那么它一定不能用太长的编码表示，否则我们的消耗实在太高了。

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为 $WPL=W_1\times L_1+W_2\times L_2+W_3\times L_3+\cdots +W_n\times L_{n}WPL=W\_1\backslash times\; L\_1+W\_2\backslash times\; L\_2+W\_3\backslash times\; L\_3+\backslash cdots+W\_n\backslash times\; L\_n$，$NN$ 个权值 $W_i(i=1,2,\cdots n)W\_i(i=1,2,\backslash cdots\; n)$ 构成一棵有 $NN$ 个叶结点的二叉树，相应的叶结点的路径长度为 $L_i(i=1,2,\cdots n)L\_i(i=1,2,\backslash cdots\; n)$。可以证明哈夫曼树的 $WPLWPL$ 是最小的。

事实上根据我们这道题的性质，任何一个字符串不能有它的前驱出现，也能发现类似的结论：所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。

那么解决这道题只需要把哈夫曼树的板子（优先队列实现）粘上来就好了，注意到每个字符出现次数用 桶 来统计一下即可：

#include<queue>
#include<cstdio>
#include<cstring>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 5e6 + 5;
char s[N]; int tot[1 << 8];
std::priority_queue<int, std::vector<int>, std::greater<int> >Q;
signed main(){
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	for (int i = 1; i <= len; ++i)
		++tot[s[i]];
	for (char c = 'a'; c <= 'z'; ++c)
		if (tot[c]) Q.push(tot[c]);
	int ans = 0;
	if (Q.size() == 1) { print(len); return 0; }
	while (Q.size() > 1) {
		int x = Q.top(); Q.pop();
		int y = Q.top(); Q.pop();
		ans += x + y;
		Q.push(x + y);
	}
	print(ans), putchar('\n');
}