算法

(贪心) $O(tn\log n)$

可以考虑每一行尽可能放宽度大的矩形。

具体实现：

• 先对所给的矩形按其宽度从大到小的顺序排序；
• 开一个带有大顶堆的优先队列来存每一行剩余空间的宽度，这一部分以后可能还会用到；
• 初始时先把 $0$ 压入大顶堆，表示当前没有剩余空间；
• 然后扫描一下所有的矩形宽度，同时取出大顶堆的队头元素 $x$ （即剩余空间最大的那一行的所剩空间） 并弹出。如果当前矩形宽度比 $x$ 大的话，说明还需要一行，对答案 +1 跳到下一行即可，并把 $x$ 和 $w - a_i$ 都压入大顶堆（把 $x$ 重新压入大顶堆指的是之前剩余空间最大的那一行剩余的 $x$ 的空间没有使用，把 $w - a_i$ 压入大顶堆表示当前剩余空间最大的那一行还有 $w - a_i$ 的剩余空间可以使用）；否则的话就把 $x - a_i$ 压入大顶堆（表示当前剩余空间最大的那一行还剩 $x - a_i$ 的空间可利用）。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using std::priority_queue;

int main() {
    int t;
    cin >> t;

    while (t--) {
        priority_queue<int> q;
        q.push(0);
        int n, w;
        cin >> n >> w;
        vector<int> a(n);
        rep(i, n) cin >> a[i];
        sort(a.rbegin(), a.rend());
        int ans = 0;
        rep(i, n) {
            int x = q.top(); q.pop();
            if (x < a[i]) {
                q.push(x);
                q.push(w - a[i]);
                ans++;
            }
            else q.push(x - a[i]);
        }
        cout << ans << '\n';
    }

    return 0;
}