by AHdoc

1001[J]

1002[G]

1003[J]

1004[J]

1005[G]

1006[J]

1007[G]

k叉哈夫曼树问题,求在给定的最大代价T下最小的k

二分k
用优先队列合并 $O(n log^2n)$ TLE

然而利用单调性有个$O(n)$的做法
即先将所有数排序,另一个队列维护合并后的值
每次从两个序列取最小值即可
注意如果 $n \pmod{k-1} \not{=} 1$,即最后一次合并不能有k个
那就将这些数放到第一个来合并,有$n \pmod{k-1} (if =0 + (k-1))$个

复杂度$O(n\log{n})$

1008

1009[J]

1010

1011[J]

1012