题目大意
给定 (n) 个能量块,每个能量块有一个正整数能量 (a_i)。现在需要凑出总能量至少为 (S)。每次可以选一个能量块加入,求最少需要选多少个能量块能使能量和达到或超过 (S)。
思路
在维护星际飞船的能量核心时,工程师发现了 n 个备用能量块。第 i 个能量块输出的能量为 ai。飞船启动需要总能量不低于 S。你可以选取一些能量块,将它们输出的能量累加。由于能量块使用得越多,能量耦合损耗越大,你希望用尽可能少的能量块来满足启动要求。请你计算最少需要多少个能量块。
保证:能量块的数量 n 满足 1≤n≤20000,目标能量 S 满足 1≤S≤∑ai≤2000000007,每个能量块的能量 ai 满足 1≤ai≤10000。
第一行包含两个整数 n 和 S。接下来的 n 行,每行包含一个整数 ai,表示一个能量块的能量。
输出一个整数,表示最少需要多少个能量块,使得其能量之和不小于 S。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.