题解

k叉哈夫曼树，但是没有了二叉那样的最后一定能合并成一个树根的优秀性质，我们就不断模拟操作看看到了哪一步能用的节点数< k，然后先拿这些节点数合并起来

然后就可以k个k个合并了，大小一样先拿深度小的

代码

#include 
    
     //#define ivorysi#define enter putchar('\n')#define space putchar(' ')#define fi first#define se second#define pb push_back#define mp make_pair#define eps 1e-8#define mo 974711#define MAXN 100005#define pii pair
     
      using namespace std;typedef long long int64;typedef double db;template
      
       void read(T &res) {    res = 0;char c = getchar();T f = 1;    while(c < '0' || c > '9') {    if(c == '-') f = -1;    c = getchar();    }    while(c >= '0' && c <= '9') {    res = res * 10 + c - '0';    c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {putchar('-');x = -x;}    if(x >= 10) {    out(x / 10);    }    putchar('0' + x % 10);}int N,K;int64 W[MAXN],ql,qr,Q[MAXN],l1,ans,dep[MAXN];void Solve() {    read(N);read(K);    for(int i = 1 ; i <= N ; ++i) read(W[i]);    sort(W + 1,W + N + 1);    l1 = 1;ql = 1,qr = 0;    int t = N;    while(t >= K) t = t - K + 1;    if(t != 1) {    for(int i = 1 ; i <= t ; ++i) {        ans += W[i];        ++l1;    }    Q[++qr] = ans;    dep[qr] = 1;    }    t = N - t + 1;    while(t != 1) {    int64 tmp = 0,d = 1;    for(int j = 1 ; j <= K ; ++j) {        int64 t;        if(ql <= qr && l1 <= N) {        if(W[l1] <= Q[ql]) t = W[l1],++l1;        else t = Q[ql],d = max(d,dep[ql] + 1),++ql;        }        else if(ql <= qr) {        t = Q[ql],d = max(d,dep[ql] + 1),++ql;        }        else t = W[l1],++l1;        tmp += t;    }    ans += tmp;    Q[++qr] = tmp;    dep[qr] = d;    t = t - K + 1;    }    out(ans);enter;out(dep[qr]);enter;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}