题目大意
给定 (n) 头牛,每头牛有一个正整数“高度” (h_i)。现在需要凑出总高度至少为 (b) 的“牛队伍”。每次可以选一头牛加入队伍,求最少需要选多少头牛能使高度和达到或超过 (b);
思路
- 排序:根据“贪心”思想,优先选高度最高的牛才能最快凑够高度。因此,将所有牛的高度按 降序 排列。
- 累加:从最大的开始,依次累加高度,并记录已经选了多少头牛。
- 判断:每次累加后检查当前总高度是否已达标,若达标则返回已选牛的数量;遍历结束后依然未达标,则返回 (-1)。
P2869.第1题-书架
题目内容
农场主约翰最近为牛牛图书馆买了一个书架,但是书架很快就要被装满了,目前只剩下最顶端的位置。
好在约翰有n头牛,第i头牛的高度是hi。
书架的高度是b,为了到达最顶端,牛牛们可以一只踩另外一只,堆叠起来,总高度是这些牛牛的高度之和。到达是指,总高度大于等于书架的高度。
越多牛牛会越不稳定,所以约翰想问你,最少多少只牛牛可以完成任务。
输入描述
第一行有两个整数n,b(1≤n≤20000),(1≤b≤∑hi≤2000000007)。
随后n行,每行一个整数hi(1≤hi≤10000)。
输出描述
输出一个整数,代表最少多少只牛牛可以完成任务、
示例1
输入
6 40
6
08
11
13
19
11
输出
3
说明
其中一种解决方案是18+11+13=42>40。