并不是很想写概述啊。
这不是权限题，来个链接大家自己看下吧：题目传送门
相信大家看来这道题之后都不难联想到哈夫曼编码的原理。
Ps：不知道哈夫曼编码，问度娘去吧。
这么看来这道题转变为另外一个问题：
求一棵K叉哈夫曼树的最小值，并使树的深度最小。
首先考虑解决K叉问题，如果是二叉，我们选最小和次小，如果是K叉显然是选择前K小的数合并。但是又存在一个问题，最后剩下的节点个数不一定能被k-1整除，这其实不难思考，刚开始合并的时候补权值为0的节点，因为0点在任意一层对答案都不会造成影响，且能使最后的哈夫曼树是完全K叉树。
接下来考虑深度最小，这个也很简单，堆比较时多开一个d表示深度就可以了。
#include<cstdio> #include<queue> #define LL long long using namespace std; const int maxn=100005; struct jz{ int d; LL x; bool operator<(const jz &b)const{ if (b.x==x) return d>b.d; return x>b.x; } }; inline LL _read(){ LL num=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') num=num*10+ch-48,ch=getchar(); return num; } priority_queue<jz> heap; int n,k,a[maxn]; LL ans; int max(int x,int y){if (x>y) return x;return y;} int main(){ freopen("exam.in","r",stdin); freopen("exam.out","w",stdout); n=_read(),k=_read(); for (int i=1;i<=n;i++){ jz x;x.x=_read();x.d=0; heap.push(x); } if (k>2) while(n%(k-1)!=1) n++,heap.push((jz){0,0}); for (int i=1;i<=n/(k-1)-(k==2);i++){ jz h;h.x=h.d=0; for (int j=1;j<=k;j++) h.x+=heap.top().x,h.d=max(h.d,heap.top().d+1),heap.pop();//printf("%lld %d ",heap.top().x,heap.top().d), ans+=h.x;heap.push(h); } printf("%lld\n",ans); printf("%d\n",heap.top().d); return 0; }