原题链接

题解

1.该题等价于构建一颗k叉树，每个叶子节点都有一个权值 \(leaf_i\) ，树的权值为 \(\sum_{1}^{n}leaf_i\) ，在使树的权值尽可能小的情况下，使最深的叶子节点的深度也尽可能小，即使数的高度尽可能小
这个叫做哈夫曼树

2.构建过程如下：每次从队列中取出 \(k\) 个节点，然后把他们合并成一个节点，在放回队列中。直至最后只剩下1个节点。
但是队列到最后可能剩下大于1，小于k个节点，也就是说，最高层的k叉树是不满的，这样显然不优，因为越高层的叶子节点对数的总权值贡献越小
解决方法是一开始往队列里加权值为0的叶子节点，这些叶子节点会优先布满最底层，然且不对树权值造成影响

code

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

inline void read(ll &x) {
	x = 0;
	ll flag = 1;
	char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
	while(c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
    	putchar('-');
		x = -x;
	}
    if(x > 9)
		write(x / 10);
    putchar(x % 10 + '0');
}

struct node
{
    ll val, layer;
    bool operator<(const node &b) const
    {
        if(b.val!=val) return b.val<val;
        return b.layer<layer;
    }
};

int main()
{
    ll n, k;
    read(n);
    read(k);
    priority_queue<node> q;

    for(ll i = 1; i <= n; i++)
    {
        ll x;
        read(x);
        q.push({x, 1});
    }

    while((q.size() - 1) % (k - 1) != 0)  q.push({0, 1});

    ll ans1 = 0, ans2 = 0;
    while(q.size() != 1)
    {
        ll sum = 0, height = 0;

        for(ll i = 1; i <= k; i++)
        {
            sum += q.top().val;
            height = max(height, q.top().layer);
            q.pop();
        }
        q.push({sum, height + 1});
        ans1 += sum;
        ans2 = max(ans2, height);
    }

    write(ans1);
    putchar('\n');
    write(ans2);
    return 0;
}