注意到这个编码其实就是哈夫曼编码，考虑构造哈夫曼树。

每次就是把 $\le k$ 个并在一起，直到最后只剩下一项。

第一次把 $(n-1)\bmod(k-1)+1$ 个并在一起（如果 $k-1\nmid n-1$），之后每次并 $k$ 个，这样显然最优。

拿一个小根堆维护一下，每次取出前 $k$ 个合一起，即可 $O(n\log n)$ 求出最小解。

考虑如何最小化最长串。

考虑在状态中同时记录合并次数，如果有相同的大小优先取合并次数少的。可以证明这样最优。

总复杂度 $O(n\log n)$。

参考代码。