题解

算法分析

本题是一个典型的 k 叉哈夫曼树（Huffman Coding） 问题，属于 贪心算法 和 树结构 的应用。

问题本质

我们需要构造一棵 $k$ 叉树，使得：

1. 每个叶子节点代表一种单词，权值为出现次数 $w_i$
2. 每个内部节点的权值为其所有子节点权值之和
3. 目标是最小化 $\sum (w_i \times \text{depth}_i)$，即编码后的总长度
4. 在总长度最小的前提下，最小化树的高度（最长编码长度）

解题思路

1. 补足节点：

   • 对于 $k$ 叉哈夫曼树，需要满足 $(n-1) \bmod (k-1) = 0$
   • 如果条件不满足，补充权值为 $0$ 的虚拟节点

2. 构建哈夫曼树：

   • 使用最小堆（优先队列）维护当前所有树的根节点
   • 每次取出权值最小的 $k$ 棵树，合并成一棵新树
   • 新树的权值为 $k$ 棵子树权值之和
   • 重复直到只剩一棵树

3. 计算答案：

   • 通过 DFS 计算每个叶子节点的深度
   • 总长度 = $\sum (w_i \times \text{depth}_i)$
   • 最长编码长度 = 树的高度

算法标签

• 哈夫曼编码（Huffman Coding）
• 贪心算法（Greedy）
• k 叉树构造
• 优先队列（堆）

关键代码解析

// 补足节点以满足k叉树条件
while ((n - 1) % (k - 1) != 0) {
    node tmp;
    tmp.w = 0;
    q.push(make_pair(0, tr.size()));
    tr.push_back(tmp);
    n++;
}

// 构建哈夫曼树
while (n > 1) {
    ull cnt = 0;
    node tmp;
    
    // 取出k个最小权值的树
    for (ull i = 1; i <= k; i++) {
        cnt += q.top().first;
        tmp.kids.push_back(q.top().second);
        q.pop();
    }
    
    tmp.w = cnt;
    q.push(make_pair(cnt, tr.size()));
    tr.push_back(tmp);
    n -= k - 1;  // 每次合并减少k-1棵树
}

// 计算深度和答案
dfs(q.top().second);  // 从根节点开始DFS
ull cnt = 0, ans = vis[1];
for (ull i = 0; i < tr.size(); i++) {
    if (tr[i].kids.empty())  // 叶子节点
        cnt += tr[i].w * vis[i];
    ans = max(ans, vis[i]);  // 最大深度
}

时间复杂度

• 建堆：$O(n \log n)$
• 哈夫曼树构建：$O(n \log n)$（每次堆操作 $O(\log n)$，共 $O(n)$ 次）
• DFS 遍历：$O(n)$
• 总体复杂度：$O(n \log n)$，能够处理 $n \leq 10^5$ 的数据规模

空间复杂度

• $O(n)$，用于存储树结构和深度信息

算法正确性证明

哈夫曼树的贪心选择性质保证了总编码长度最小：

• 每次合并权值最小的 $k$ 棵树，可以证明这种策略能得到最优解
• 补充虚拟节点保证了每次都能进行 $k$ 路合并
• 深度计算保证了在总长度最小的前提下找到高度最小的方案

总结

本题通过构造 $k$ 叉哈夫曼树解决了最优前缀编码问题，是贪心算法的经典应用。关键在于理解 $k$ 叉哈夫曼树的构造条件和合并策略，以及如何通过补充虚拟节点来满足构造条件。