题目链接

解题思路

??将所有的字符串编码看成是一棵trie，因为所有的字符串都不互为前后缀，所以每一个字符串都末尾都位于trie的叶子结点上。
??因为要确保总长度最小，所以对于出现次数越多的字符串，其叶子在trie上的深度就越浅，那么出现次数越少的字符显然其叶子深度也就越深。所以可以用出现次数做权值，用优先队列来合并叶子结点并生成父节点。并且为了保证权值大的点尽量靠近根，我们用权值为0的点对叶子做填充，使整个树为一个满k叉树。
??最后还有一个问题，如何确保最长的字符串编码最短。举个例子，k=3的时候有3个权值为2个结点，1个深度为3，另外两个深度为0，那么让两个深度为0的结点结合，更有希望让整个树的树高更低。即对于权值相同的点优先合并深度最浅的。

代码

const int maxn = 1e4+10;int n,k; P t[20];int main(){ scanf("%d%d",&n,&k); priority_queue<P,vector<P>,greater<P> > pq; for (int i = 0; i<n; ++i) { ll num; scanf("%lld",&num); pq.push({num,0}); } for (int i = 0; (n-1)%(k-1)&&i<k-1-(n-1)%(k-1); ++i) pq.push({0,0}); ll ans1 = 0; while(pq.size()>1) { ll res = 0; int maxx = 0; for (int i = 0; i<k; ++i) { res += pq.top().first; maxx = max(maxx,pq.top().second); pq.pop(); } ans1 += res; pq.push({res, maxx+1}); } printf("%lld\n%lld\n",ans1,pq.top().second); return 0;}