题解：CF1498B Box Fitting

题目大意

要求找到一个最小高度的二维盒子，使得

n

个给定的宽度为

2

的方幂的长条能够在不旋转、不重叠的情况下放入宽度为

w

的盒子之中。

题目解法

只要直到答案可以简单判断出是否满足题目要求，所以采用二分解决。
二分范围：因为最多需要 $n$ 层用来放置长条，所以二分范围是从 $1$ 到 $n$ 。
对于二分到的答案 $mid$ ，用一个大根堆来模拟将所有长条放入长度为 $mid$ ，宽度为 $W$ 的盒子是否满足条件。
如果答案合法根据题目要求尝试更小的值，否则尝试更大值让答案尽可能满足。

给出代码

CPP

#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;
}

题解：CF1498B Box Fitting

文章操作

题目大意

题目解法

给出代码

相关推荐

评论

题解：CF1498B Box Fitting