题目描述
难度分:1300
输入T(≤5000)表示T组数据。所有数据的n之和≤105。
每组数据输入n(1≤n≤105),w(1≤w≤109)和长为n的数组a(1≤a[i]≤106)。
保证a[i]都是2的幂。保证max(a)≤w。
有n个物品,第i个物品的体积是a[i]。至少要多少个容量为w的背包,才能装下这n个物品?
输入样例
2
5 16
1 2 8 4 8
6 10
2 8 8 2 2 8
输出样例
2
3
算法
贪心
先将a数组排序,然后优先对体积大的物品装箱。用一个大根堆heap存储所有背包的剩余空间,分为以下几种情况:
- 当heap为空时,直接插入w−a[i]。
- 否则弹出堆顶v,如果v≥a[i],说明空间足够,把a[i]放入这个背包,把v−a[i]压入堆中。否则说明剩余空间最多的背包也装不了a[i],开一个新的背包,把v压回堆中,并再压一个w−a[i]进去。
最后堆的大小就是最少用的背包个数。
复杂度分析
时间复杂度
对a数组排序的时间复杂度为O(nlog2n)。接下来倒序遍历a,对每个物品装箱,涉及到往堆中插入元素的操作,每个物品的装箱在最差情况下时间复杂度为O(log2n),一共n个物品,时间复杂度还是O(nlog2n)。
空间复杂度
空间消耗主要在于大根堆,其中的元素数量在O(n)级别,这也是整个算法的额外空间复杂度。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int T, n, w, a[N];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &w);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
priority_queue<int> heap;
int rest = w;
for(int i = n; i >= 1; i--) {
if(heap.empty()) {
heap.push(w - a[i]);
}else {
int v = heap.top();
if(v >= a[i]) {
heap.pop();
heap.push(v - a[i]);
}else {
heap.push(w - a[i]);
}
}
}
printf("%d\n", heap.size());
}
return 0;
}