哈夫曼树

对于任意的 1≤i,j≤n，i≠j，都有：si 不是 sj 的前缀 这就是说要用到哈夫曼树
题目还要保证最长的字符串长度最小，那么如果现在有两个权值相同的节点，我们应该优先选择深度较小的节点，因为我们如果选择了深度大的节点那么这个树的深度就会变长，我们选中深度较小的节点，那么我们深度较大的节点会在后面安排上，比当前选择优。
在用scanf printf 输入数据时一定要注意这个数时 long long 还是 int
在用scanf printf 输入数据时一定要注意这个数时 long long 还是 int
在用scanf printf 输入数据时一定要注意这个数时 long long 还是 int
在用scanf printf 输入数据时一定要注意这个数时 long long 还是 int
在使用结构体函数直接赋值时也要注意 { 0ll,0 } 0之后的 ll 一定不能忘记
在使用结构体函数直接赋值时也要注意 { 0ll,0 } 0之后的 ll 一定不能忘记
在使用结构体函数直接赋值时也要注意 { 0ll,0 } 0之后的 ll 一定不能忘记

#include<bits/stdc++.h>
#define pr printf
#define sc scanf
#define fur(i,a,b) for(int i = a; i<= b ;i++)
#define fdr(i,a,b) for(int i = a; i>= b ;i--)
using namespace std;
typedef long long ll;
const int N = 100000 + 5 ;
typedef pair<ll , int > PLI;
int n,k;
priority_queue< PLI, vector <PLI> ,greater <PLI> >q;
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d %d",&n,&k);
    for(int i = 0 ; i < n ; i++){
        ll x;
        scanf("%lld",&x);
        q.push({x,0});
    }
    ll res = 0 , ma = 0 ;
    while(( q.size() - 1) %  (k - 1) !=0)
    {
        q.push({0ll,0});
    }

    while(q.size() > 1){
        ll sum = 0 ;
        int dep = 0;
        for(int i = 0 ;i < k ;i++)
        {
            sum +=q.top().first;
            dep = max(dep , q.top().second);
            q.pop();
        }
        res += sum;
        q.push( {sum, dep + 1});
    }
    printf("%lld\n%d",res,q.top().second);
    return 0;
}