------------恢复内容开始------------

问题转化

\(Huffman\)编码

\(Huffman\)编码即通过统计字符串中不同字符所出现的次数作为叶节点构造一棵\(Huffman\)树。把这个\(Huffman\)树看成一棵\(Trie\)，在\(k\)叉\(Huffman\)中不同分支对应着不同的\(k\)进制数，从根节点开始遍历路径，其从根节点到各个字符路径上的权值连起来便是这个字符的\(Huffman\)编码（即\(S_i\)），而在\(Trie\)中所有的单词编码的末尾都在叶节点上，而不在内部节点上，因此一个字符不会是另一个字符的前缀。但是其同种数据可能对应不同的编码，且\(Huffman\)树的带权路径长度\(（WPL）\)都是相同的。

题意分析

根据题意的暗示，我们本题所采用的编码方式为\(Huffman\)编码，所求的问题为：求出一个\(k\)叉\(Huffman\)树，在保证其权值尽量小的情况下，使得\(Huffman\)树的深度尽量小。（第一行输出\(WPL\)，第二行输出树的深度）

思路

因为我们要让我们所够造的\(Huffman\)树的深度尽量小，所以我们在求\(Huffman\)树时，对于权值相同的节点需要优先合并当前深度最小的分支（即让深度较大的分支后合并使其尽量向上，树的深度尽量小）。而如果当前的元素个数不能够造一棵完全\(k\)叉树，添加\(m\)个权值为\(0\)的虚节点处理。

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<LL,int> PLI;


int n,k;
priority_queue<PLI,vector<PLI> ,greater<PLI>> heap;

int main(){
    scanf("%d%d",&n,&k);
    for (int i = 0; i < n; i++){
        LL x;
        scanf("%lld",&x);
        heap.push({x,0});
    }
    while ((n - 1) % (k - 1) != 0)heap.push({0,0}),n++;
    LL ans = 0;
    while(heap.size() > 1){
        int h = 0;
        LL d = 0;
        for (int i = 0; i < k; i++){
            d += heap.top().first;
            h = max(h,heap.top().second + 1);
            heap.pop();
        }
        heap.push({d,h});
        ans += d;
    }
    cout << ans << endl << heap.top().second; 
    return 0;
}

------------恢复内容结束------------