1045. 箱子打包

单点时限: 2.0 sec

内存限制: 256 MB

有一组 1 维的物品需要打包进一批同样的箱子中。所有的箱子有完全一样的长度 l 以及每一个物品长度 li<=l. 我们要找到一个最小的数字 q, 使得 :

(1) 每个箱子最多包含两个物品

(2) 每个物品要被包含在 q 个箱子中的一个中

(3) 在箱子中物品的总长度不能超过 l

你的任务是,给定 n 个整数,l,l1,l2....ln, 计算最小的箱子总数 q.

输入格式

第一行包含一个数字 n(1<= n <= 10^5), 表示有几个物品。第二行包含一个整数表示了箱子的长度 l (l<=10000). 接下去的 n 行是表示了每个物品的长度。

输出格式

输出一个整数,表示能够包含所有物品的最小的箱子总数。
提示 :

The sample instance and an optimal solution is shown in the figure below. Items are numbered from 1 to 10 according to the input order.

样例

Input
10
80
70
15
30
35
10
80
20
35
10
30
Output
6

111 人解决,144 人已尝试。

157 份提交通过,共有 510 份提交。

3.4 EMB 奖励。

创建: 13 年,9 月前.

修改: 2 年,5 月前.

最后提交: 2 周前.

来源: N/A

题目标签