HDU-5884 Sort

题目大意：

给你n个长度为ai的序列，让你把这n个序列合并，每次合并需要一个cost，值为合并的序列的长度之和，每次最多可以合并k个序列。现在问你，给出cost最大为T，最小的k是多少。

解题思路：

显然，可以用优先队列水一发，复杂度为nlognlogn

二分枚举k，然后每次取最小的k个加在一起，加入队列，然后判断，加和是否比T大。

其实就是一个k维哈夫曼树的优先队列优化，来篇博客，传送门

代码：

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long LL;

const int maxn = 100005;

int a[maxn];
int n, t, cas;

int Scan() {
	int res = 0, ch, flag = 0;
	if ((ch = getchar()) == '-')
		flag = 1;
	else if (ch >= '0'&&ch <= '9')
		res = ch - '0';
	while ((ch = getchar()) >= '0'&&ch <= '9')
		res = res * 10 + ch - '0';
	return flag ? -res : res;
}
void Out(int a) {
	if (a > 9)
		Out(a / 10);
	putchar(a % 10 + '0');
}
bool judge(int k) {
	LL sum = 0, pre = 0;
	int inx = 0, cnt = 0;
	priority_queue<LL, vector<LL>, greater<LL> > q;
	if ((n - 1) % (k - 1)) {
		for (int i = 0; i < ((k - 1) - (n - 1) % (k - 1)); ++i) q.push(0);
	}
	while (inx < n) {
		if (cnt < k) {
			if (!q.empty() && q.top() < a[inx]) {
				pre += q.top(); q.pop();
				++cnt;
			} else {
				pre += a[inx++];
				++cnt;
			}
		} else {
			cnt = 0;
			if (sum + pre > t) return false;
			sum += pre;
			q.push(pre); pre = 0;
		}
	}
	while (!q.empty()) {
		if (cnt < k) {
			pre += q.top(); q.pop();
			++cnt;
		} else {
			cnt = 0;
			sum += pre;
			if (sum > t) return false;
			q.push(pre); pre = 0;
		}
	}
	if (sum + pre > t) return false;
	return true;
}
int main() {
	cas = Scan();
	while (cas--) {
		n = Scan(); t = Scan();
		for (int i = 0; i < n; ++i)
			a[i] = Scan();
		sort(a, a + n);
		int l = 0, r = n, mid;
		while (l < r) {
			mid = (l + r) >> 1;
			if (judge(mid)) r = mid;
			else l = mid + 1;
		}
		Out(r); puts("");
	}
	return 0;
}