题解：CF1498B Box Fitting

cyntmeay · 2025-09-05 14:50:15 · 题解

题目大意

要求找到一个最小高度的二维盒子，使得 n 个给定的宽度为 2 的方幂的长条能够在不旋转、不重叠的情况下放入宽度为 w 的盒子之中。

题目解法

• 只要直到答案可以简单判断出是否满足题目要求，所以采用二分解决。

• 二分范围：因为最多需要 n 层用来放置长条，所以二分范围是从 1 到 n。

• 对于二分到的答案 mid，用一个大根堆来模拟将所有长条放入长度为 mid ，宽度为 W 的盒子是否满足条件。

• 如果答案合法根据题目要求尝试更小的值，否则尝试更大值让答案尽可能满足。

给出代码

#include <bits/stdc++.h>
using namespace std;
int t, n, w, a[100005];
int calc (int h){
    priority_queue <int> q;
    for (int i = 1; i <= h; i++)
        q.push (w);
    for (int i = 1; i <= n; i++){
        if (q.top() < a[i] || q.empty()){
            return 0;
        }
        if (q.top() > a[i]){
            q.push (q.top() - a[i]);
            q.pop();
        } 
        else{
            q.pop();
        }
    }
    return 1;
}
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 + 1 + n, greater<int>());
        int l = 1, r = n + 1;
        while (l < r){
            int mid = (l + r) >> 1;
            if (calc(mid))
                r = mid;
            else
                l = mid + 1;
        }
        printf ("%d\n", l);
    }
    return 0;
}