题目链接：https://vjudge.net/contest/373557#problem/I

题目大意：求 重新编码后的 最短长度 和 重新编码后的 最长字符串的长度

数据结构刚学了Huffman树，比赛就考到了Huffman编码，在这里整理一下。

Huffman树是最优二叉树，这道题相当于最优k叉树，但是又有些不同。

不会Huffman树的可以从百度搜索，这里就不具体讲了。

Huffman树是在队列中挑出最小的两个权值组成一新节点，并放入队列中。

在这道题里面，并不是二进制，而是K进制，所以想要用到Huffman树，必须要满足(n-1)%(k-1)==0，这个条件的意思就是：最后合并的时候肯定能满足只剩k个节点，刚好能合并成最后一个节点。（不行的话，可以自己举几个例子试试）

如果不满足这个条件的话就要把{0,0}代替节点输进去。

这道题还要用到优先队列，我有一条龙服务，不会优先队列的，我博客里面有关于优先队列的单独一篇，下面给链接：https://blog.nowcoder.net/n/ad8e1df876064b0a8a3034b7df74f35d

这里优先队列的应用就是把节点中权值小的放到前面,如果权值一样的话，就把深度小的放到前面。

用一个while循环，直到优先队列中只剩下最后一个元素的时候，结束循环。（这里要注意不是优先队列为空的时候，是优先队列大小为1的时候停止循环）

循环里面就是每k个为一组，把长度值加起来并加到要输出的最终长度值上，把三个的深度求出最大值，结束for循环对输出的最短长度进行优化。

下面是AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
using namespace std;
struct sss{
    long long x,h;
    bool operator <(const sss & y) const
    {
        if(x!=y.x) return x>y.x;
        else return h>y.h;
    }
}p;
int main()
{
    long long n,k,x;
    cin >> n >> k;
    priority_queue<sss>q;
    for (int i=1;i<=n;i++)
    {
        cin >> x;
        q.push({x,0});
    }
    while((n-1)%(k-1)!=0)
    {
        n++;
        q.push({0,0});
    }
    long long ans1=0;
    long long ans2=0;
    while(q.size()>1)
    {
        long long xx=0;
        long long hh=0;
        for (int i=1;i<=k;i++)
        {
            p=q.top();
            cout << p.h << " " << p.x << endl;
            q.pop();
            hh=max(p.h,hh);
            xx+=p.x;
        }
        ans1+=xx;
        ans2=max(ans2,hh+1);
        q.push({xx,hh+1});
    }
    cout << ans1 << endl << ans2 << endl;
    return 0;
}