#1045. 「USACO 2012.3 Gold」Cows in a Skyscraper

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
skyscraper.in ≫ skyscraper.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

一个鲜为人知的事实是,Bessie 和她的朋友们喜欢爬楼梯比赛。一个更为人知的事实是,奶牛们真的不喜欢下楼梯。因此,当奶牛们比赛到达她们最喜欢的摩天大楼的顶层后,她们遇到了一个问题。拒绝使用楼梯下楼,奶牛们被迫使用电梯返回地面层。

电梯的最大载重量为 ,奶牛 的体重为 。请帮助 Bessie 找出如何用最少的电梯次数将所有 头奶牛 送到地面层。每次电梯的总重量不能超过

输入格式 skyscraper.in

* 第 1 行:用空格分隔的

* 第 2 行到第 行:第 行包含一个整数 ,表示一头奶牛的体重。

输出格式 skyscraper.out

* 一个整数 ,表示所需的最少电梯次数。

样例

输入 #1

4 10 
5 
6 
3 
7

输出 #1

3

数据范围与提示

有四头奶牛,体重分别为 5、6、3 和 7 磅。电梯的最大载重量为 10 磅。

我们可以将体重为 3 的奶牛与其他任何一头奶牛放在同一个电梯上,但其他三头奶牛太重,无法组合在一起。对于上述解决方案,电梯行程 1 包括奶牛 #1 和 #3,电梯行程 2 包括奶牛 #2,电梯行程 3 包括奶牛 #4。对于此输入,还有其他几种可能的解决方案。 (由 ChatGPT 4o 翻译)