哈夫曼树。
如果要最大的深度最小，再按h排序即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxv 100500
#define maxe 1000500
using namespace std;
long long n,k,val[maxv*],nume=,g[maxv*],tot,sum=,dis[maxv*],fath[maxv*];
struct edge
{
long long v,nxt;
}e[maxe];
struct status
{
long long val,pnt,h;
};
bool operator <(status x,status y)
{
if (x.val!=y.val) return x.val>y.val;
return x.h>y.h;
}
priority_queue <status> q;
void addedge(long long u,long long v)
{
e[++nume].v=v;
e[nume].nxt=g[u];
g[u]=nume;
}
void dfs(long long x)
{
for (long long i=g[x];i;i=e[i].nxt)
{
long long v=e[i].v;
if (v!=fath[x])
{
fath[v]=x;dis[v]=dis[x]+;
dfs(v);
}
}
}
int max(int a,int b)
{
if (a>b) return a;
return b;
}
int main()
{
scanf("%lld%lld",&n,&k);
for (long long i=;i<=n;i++)
{
scanf("%lld",&val[i]);
status s;
s.pnt=i;s.val=val[i];s.h=;
q.push(s);
}
long long ret=;
while ((n+ret-)%(k-)!=) ret++;
for (long long i=;i<=ret;i++)
{
status s;
s.pnt=n+i;s.val=;s.h=;
q.push(s);
val[n+i]=;
}
n+=ret;tot=n;
long long ret1=,ret2=;
while (q.size()>)
{
sum=;tot++;int mx=;
for (long long i=;i<=k;i++)
{
status b=q.top();q.pop();
sum+=b.val;mx=max(mx,b.h);
addedge(b.pnt,tot);addedge(tot,b.pnt);
}
status s;
s.pnt=tot;s.val=sum;s.h=mx+;q.push(s);
ret2=max(ret2,s.h);
val[tot]=;
}
dfs(tot);
for (long long i=;i<=n;i++)
ret1+=val[i]*dis[i];
printf("%lld\n%lld\n",ret1,ret2);
return ;
}