题目名称	148. [USACO Dec07] 书架
输入输出	`shelf.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	BYVoid 于2008-10-05加入
开放分组	全部用户
提交状态
分类标签	USACO 贪心排序
	分享题解

通过：524，提交：1056，通过率：49.62%
甘罗	100	0.000 s	0.00 MiB	Pascal
TA	100	0.000 s	0.00 MiB	Pascal
TA	100	0.000 s	0.00 MiB	Pascal
凌霄	100	0.000 s	0.00 MiB	Pascal
末#^日~`审&..判	100	0.000 s	0.00 MiB	Pascal
龙征天	100	0.000 s	0.00 MiB	C++
Regnig Etalsnart	100	0.000 s	0.00 MiB	C++
Samle	100	0.000 s	0.00 MiB	C++
雾茗	100	0.000 s	0.00 MiB	C++
锝镆氪锂铽	100	0.000 s	0.00 MiB	C++

关于书架的近10条评论(全部评论)
成功上榜 ShallowDream雨梨 2018-09-27 20:06 15楼
水题狂WA，智商下线 JustWB 2017-09-12 13:58 14楼
回复 @冰可乐w : 日常写水题降低正确率，数组不小心开爆了23333 Moon_ 2017-07-25 12:54 13楼
啊，堆的常数有毛病 HeHe 2017-02-19 15:10 12楼
帕斯卡代码看不懂QwQ，星眸初泛潋滟光 2016-07-23 08:05 11楼
不会啊 wwzdsg. 2015-11-15 21:13 10楼
脑抽把扫描顺序写反了。。。 liu_runda 2015-11-14 23:57 9楼
神奇 dateri 2015-11-04 23:42 8楼
用sort，扫一遍 flash 2015-08-09 11:02 7楼
[size=35]还是sort现成的好用[/size]。 NVIDIA 2015-07-28 12:06 6楼

148. [USACO Dec07] 书架

★★ 输入文件：shelf.in 输出文件：shelf.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

Farmer John最近为奶牛图书馆购买了一个书架，书架的下层很快装满了书，现在只剩下了顶层书架有空间。

在$n(1\leq n\leq 20000)$头牛中，第$i$头牛的身高为$h_i(1\leq h_i\leq 10000)$)。

书架的高度为$s(1\leq s\leq 2\times 10^9)$，且 $s$ 小于所有奶牛的身高之和。

书架的顶层高于最高的牛的身高，但是若干个奶牛可以站成一摞，这样总高度就是它们的身高之和。总高度应大于等于书架的高度，奶牛才能取到书。

但是越多的奶牛站成一摞，它们就越危险。你的工作就是找到一个集合，使得尽量少的奶牛站成一摞，当然，它们要能取到顶层的书。

【输入格式】

第$1$行两个整数$n,s$；

第$2$到$n+1$行，第$i+1$包含一个整数$h_i$。

【输出格式】

一行一个整数，这个使得尽量少的奶牛站成一摞取得顶层的书的集合中奶牛的个数。

【输入样例】

【输出样例】