题目描述

难度分:$1300$

输入$T(\leq 5000)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$，$w(1 \leq w \leq 10^9)$和长为$n$的数组$a(1 \leq a[i] \leq 10^6)$。

保证$a[i]$都是$2$的幂。保证$max(a) \leq 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$存储所有背包的剩余空间，分为以下几种情况：

1. 当$heap$为空时，直接插入$w-a[i]$。
2. 否则弹出堆顶$v$，如果$v \geq a[i]$，说明空间足够，把$a[i]$放入这个背包，把$v-a[i]$压入堆中。否则说明剩余空间最多的背包也装不了$a[i]$，开一个新的背包，把$v$压回堆中，并再压一个$w-a[i]$进去。

最后堆的大小就是最少用的背包个数。

复杂度分析

时间复杂度

对$a$数组排序的时间复杂度为$O(nlog_2n)$。接下来倒序遍历$a$，对每个物品装箱，涉及到往堆中插入元素的操作，每个物品的装箱在最差情况下时间复杂度为$O(log_2n)$，一共$n$个物品，时间复杂度还是$O(nlog_2n)$。

空间复杂度

空间消耗主要在于大根堆，其中的元素数量在$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;
}