HDU 5884 Sort

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5884

题目翻译

有一个长度为N的序列,合并序列总代价不能超过T,每次操作最多可以合并k个,合并的代价是这k个数字的和。求把序列合并成一个元素,且总代价不超过T的最小的k。

题解

我们首先这是合并果子问题,我们每次肯定取最小的前k个合并,但是这是刚好能合并成一个的情况,如果发现最后合并时不足k个,我们可以考虑给序列一开始补上一些不影响结果的0 。然后取前k个使用优先队列+一些小优化,因为初始的数字很小,但是数量很多,所以我们给<1000的数字计数,这样小于1000的数字出队的复杂度接近O(1) 。

代码