hdu 5884 Sort(二分+K叉哈夫曼树)

Problem Description
Recently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob receives a task from Alice.
Alice will give Bob N sorted sequences, and the i-th sequence includes ai elements. Bob need to merge all of these sequences. He can write a program, which can merge no more than k sequences in one time. The cost of a merging operation is the sum of the length of these sequences. Unfortunately, Alice allows this program to use no more than T cost. So Bob wants to know the smallest k to make the program complete in time.

 

Input
The first line of input contains an integer t0, the number of test cases. t0 test cases follow.
For each test case, the first line consists two integers N (2N100000) and T (Ni=1ai<T<231).
In the next line there are N integers a1,a2,a3,...,aN(i,0ai1000).

 

Output
For each test cases, output the smallest k.

 

Sample Input
1
5 25
1 2 3 4 5
Sample Output
3
这道题是很久写的了,然后最近碰到一个类似合并果子的题目,于是一时兴起想写个O(n)的方法,于是就把这个题回顾了一下。
这个题目一开始是直接手写堆+读入优化的做法,但是一直T,然后我换O(n)的做法来求K叉哈夫曼树,疯狂的WA。和原来的拍也拍不出错。。。比完赛才知道原来是处理K叉树未满的情况下,我的贪心错了。懊恼不已。。。
二分然后验证的思路很显然。然后O(n)求K叉哈夫曼树即可。注意如果不是正好K叉,我们需要选择最小的那几个先合并(放到哈夫曼树的底部)。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注