2323. 松鼠特攻队的“独木舟”奇袭
1000ms
256MB
简单
贪心算法
题目描述
在森林战争的关键时刻，松鼠特攻队决定通过一个无人防守的湖泊，划船偷袭敌军后方。
现在岸边一共有 $n$ 名精锐松鼠士兵，指挥官哈利已经称好了每名士兵的体重。然而现场只有一艘简陋的独木舟，其载重量非常有限（最大载重为 $W$）。由于敌军巡逻非常严密，这艘船**只能运送一次**，且必须在不超重的前提下，尽可能多地运送士兵过湖，以便在对岸形成人数优势。
请你编写程序帮哈利计算一下，这艘独木舟一次最多能运送多少名士兵？
输入格式
- 第一行包含两个正整数 $n$ 和 $W$ ($n, W < 2000$)，分别表示士兵的数量和独木舟的最大载重量。
- 第二行包含 $n$ 个正整数，表示每名士兵的体重（每名士兵体重 $< 300$）。
输出格式
- 输出一行一个整数，表示独木舟最多能装载的士兵人数。
样例 1
输入 (Input)
5 11 7 2 6 4 5
输出 (Output)
3
样例说明
独木舟最大载重为 11。将士兵体重按从小到大排序得到：`2 4 5 6 7`。
- 选择最轻的 3 名士兵：$2 + 4 + 5 = 11$，刚好不超重。
- 如果尝试装载 4 名士兵，则最小总重为 $2 + 4 + 5 + 6 = 17 > 11$，超重。
- 因此最多运送 3 名士兵。
- $n, W < 2000$
- 单个士兵体重 $< 300$
- **算法提示**：
这是一个典型的**贪心算法**问题。为了在有限的载重内装下更多的人，我们应该优先选择体重最轻的士兵。
1. 将所有士兵的体重从小到大排序。
2. 从体重最轻的士兵开始累加，直到总重量超过船的载重量为止。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功