题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5884
题目大意：有n个有序的序列，对于第i个序列有ai个元素。 现在有一个程序每次能够归并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 = 100003; int a[N], n, t; bool judge(int mid) { int cnt; if((n-1) % (mid - 1) == 0) cnt = 0; else cnt = ((n - 1) / (mid - 1) + 1 ) * (mid - 1) + 1 - n; queue<ll> que1, que2; for(int i=0; i<n; ++ i) que1.push(a[i]); ll ans = 0; ll res = 0; while((que1.size() == 1 && que2.empty() && res == 0) == 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 = 0, cnt = 0; } } if(ans <= t) return true; else return false; } void solve() { scanf("%d%d", &n, &t); for(int i=0; i<n; ++ i) scanf("%d", &a[i]); sort(a, a+n); int l = 2, r = n; while(l < r) { int mid = (l + r) >> 1; if(judge(mid)) r = mid; else l = mid + 1; } printf("%d ", l); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }