AcWing 149. 荷马史诗-526互联

题面：
一部《荷马史诗》中有 \(n\) 种不同的单词，从 \(1\) 到 \(n\) 进行编号。其中第 \(i\) 种单词出现的总次数为 \(w_i\)。用 \(k\) 进制串 \(s_i\) 来替换第 \(i\) 种单词，使得其满足如下要求：

对于任意的 \(1≤i,j≤n\)，\(i≠j\)，都有：\(s_i\) 不是 \(s_j\) 的前缀。

替换以后得到的新的《荷马史诗》长度最小。

在确保总长度最小的情况下，求出最长的 \(s_i\) 的最短长度。

原题链接：AcWing 149. 荷马史诗
参考链接：
AcWing 149. 荷马史诗(二叉堆 Huffman树贪心) - Bug-Free
AcWing 149. 荷马史诗 - 秦淮岸灯火阑珊

本题面对的两个问题：

最小权值和
最小化深度

最小权值和

\(k\) 进制编码的情况下，使用的不再是二叉哈夫曼树，而是 \(k\) 叉堆。
\(k\) 叉堆会存在的问题：只能形成完全 \(k\) 叉堆的特殊情况
- 形成满 \(k\) 叉堆的条件：
  \(n-m(k-1)=1\)
  ⇒ \(n-1=m(k-1)\)
  ⇒ \(n-1\) 为 \(k-1\) 的倍数
  ⇒ \((n-1)\%(k-1)=0\)
- 解决方法：
  - 法一：特殊处理首次合并，首次合并为 \(n-m(k-1)\) 堆，剩下合并为 \(k\) 堆。
  - 法二：为最后一层补满空结点，以让其余结点权值和最小化。

最小化深度

在建树时，新节点优先成为深度较小的结点的孩子。
如果多个点的权值相同时，优先考虑高度较低（已合并次数最少）的树。
- Q：为什么代码中使用 max(u, h.top().second) 而不是 min？
  A：因为建树的过程是从下往上的。

拓展：Huffman树与Trie树

常见应用场景

深度与权重：Huffman树
求公共前缀：Trie树

本题为何适用

本题中要求对于任意的 \(1≤i,j≤n\)，\(i≠j\)，都有 \(s_i\) 不是 \(s_j\) 的前缀。
应用Trie树：叶子结点上的字母必然互不相同；
应用Huffman树：每层至多产生一个父结点。

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 1e5 + 10;

int n, k;
LL x;

priority_queue<PLI, vector<PLI>, greater<PLI>> h;

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> x;
        h.push({ x,0 });
    }
    while ((n - 1) % (k - 1)) {
        h.push({ 0,0 });    //加入空结点
        n++;    //更新结点数
    }
    LL res = 0;
    while (h.size() > 1) {
        LL sum = 0;
        int u = 0;  //新节点的高度
        for (int i = 0; i < k; i++) {
            sum += h.top().first;   //该层的所有结点权值和
            u = max(u, h.top().second); //同权值时优先深度最小
            h.pop();
        }
        res += sum;
        h.push({ sum,u + 1 });
    }
    cout << res << endl;
    cout << h.top().second;
}

martian strings 149e cf