← 返回题目列表

Codeforces · 1498/B

B. 盒子配件

中文机器翻译题面 查看原题

给你 $$$n$$$ 个矩形,每个矩形的高度为 $$$1$$$。每个矩形的宽度是 $$$2$$$ 的幂(即,对于某些非负整数 $$$x$$$,它可以表示为 $$$2^x$$$)。

您还会获得一个宽度为 $$$W$$$ 的二维框。请注意,$$$W$$$ 可能是也可能不是 $$$2$$$ 的幂。此外,$$$W$$$ 至少与最大矩形的宽度一样大。

你必须找到这个盒子的最小高度,以便它能够适合所有给定的矩形。拟合完所有矩形后,该框中允许留有一些空白。

您无法旋转给定的矩形以使其适合框。此外,任何两个不同的矩形不得重叠,即。即,任何两个不同的矩形的交叉面积必须为零。

请参阅注释以了解示例输入的直观说明。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^3$$$) — 测试用例的数量。每个测试用例由两行组成。

对于每个测试用例:

- 第一行包含两个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) 和 $$$W$$$ ($$$1 \le W \le 10^9$$$);
- 第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 10^6$$$),其中 $$$w_i$$$ 是第 $$$i$$$ 个矩形的宽度。每个 $$$w_i$$$ 是 $$$2$$$ 的幂;
- 另外,$$$\max\limits_{i=1}^{n} w_i \le W$$$。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

输出 $$$t$$$ 整数。第 $$$i$$$ 个整数应该等于第 $$$i$$$ 个测试用例的答案 - 盒子的最小高度。

示例

输入 #1

2
5 16
1 2 8 4 8
6 10
2 8 8 2 2 8

输出 #1

2
3

注意

对于示例输入中的第一个测试用例,下图显示了将给定的五个矩形装入具有最小高度的 2D 框的一种方法:

上图中,每个矩形内部的数字就是其宽度。 2D 框的宽度为 $$$16$$$(用下面的箭头表示)。在这种情况下,2D 框所需的最小高度为 $$$2$$$(如左侧所示)。

在第二个测试用例中,通过在三个级别中的每一层上保留两个块(宽度为 8 和 2 各一个),可以使最小高度为 3。