题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5884
题目大意：有n个有序的序列，对于第i个序列有a个元素。 现在有一个程序每次能够归并k个序列， 他的花费为k个序列中的总的元素数。现在想知道在花费不超过t的情况下存在的最小的k为多少？
解题思路：二分k的值，合并k个序列的值， 加入队列，然后用哈夫曼检查最小花费是否超过t！ 这时需要注意最后一次合并是否为k个数， 如果不是k个数，就不是最优的哈夫曼的值， 如果最后是k个数， 那么最后n， k一定符合（n-1）%（k-1） == 0， 只需在二分出k的值时判断一下， 如果不是0的话， 可以对前面进行补0操作， 这样得的值是最优的（可以自行搜索k叉哈夫曼树）。
关于怎么快速计算哈夫曼的值，可以用两个队列维护两个有序的序列， 可以在O（n）的时间内得出哈夫曼的值（注：优先队列不可以， n*log（n）这题会超时）
代码如下：
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = ; int a[N], n, t;
bool judge(int mid)
{
int cnt;
if((n-) % (mid - ) == )
cnt = ;
else
cnt = ((n - ) / (mid - ) + ) * (mid - ) + - n;
queue<ll> que1, que2;
for(int i=; i<n; ++ i)
que1.push(a[i]);
ll ans = ;
ll res = ;
while((que1.size() == && que2.empty() && res == ) == false)
{
if(!que1.empty() && !que2.empty())
{
if(que1.front() > que2.front())
{
res += que2.front();
que2.pop();
}
else
{
res += que1.front();
que1.pop();
}
}
else if(!que1.empty() && que2.empty())
{
res += que1.front();
que1.pop();
}
else if(que1.empty() && !que2.empty())
{
res += que2.front();
que2.pop();
}
cnt ++; if(cnt == mid)
{
ans += res;
if(que1.size())
{
if(que1.back() <= res)
que1.push(res);
else
que2.push(res);
}
else
que1.push(res);
res = , cnt = ;
}
}
if(ans <= t)
return true;
else
return false;
} void solve()
{
scanf("%d%d", &n, &t);
for(int i=; i<n; ++ i)
scanf("%d", &a[i]);
sort(a, a+n);
int l = , r = n;
while(l < r)
{
int mid = (l + r) >> ;
if(judge(mid))
r = mid;
else
l = mid + ;
}
printf("%d\n", l);
} int main()
{
int T;
scanf("%d", &T);
while(T--)
{
solve();
}
return ;
}