2325. 松鼠特工的“防空洞”紧急会议
1000ms
256MB
简单
贪心算法
题目描述
在魔法森林里，松鼠特工队经常遭受来自老鹰军团的空袭。经过长期观察，哈利队长总结出了一套经验：每天都有一段宝贵的“安全时段”（例如：5 点到 9 点是安全时段，则 $9 - 5 = 4$ 小时内不会遭到空袭）。
各大特工分部都想在这个安全时段内召开紧急作战会议，但条件有限，森林里只有一间隐蔽的防空会议室。
- **会议要求**：各分部对会议的开始时间没有固定要求，只要在安全时段内开完即可。
- **上报信息**：每个分部只上报了自己会议所需的持续时长（小时）。
请你帮哈利队长算一算，在这个有限的安全时段内，怎么安排才能开成**最多**场次的作战会议？
输入格式
- 第一行包含三个正整数：安全时段的开始时间 $S$、结束时间 $E$，以及分部数量 $n$ ($n \le 24$)。
- 第二行包含 $n$ 个正整数，表示每个分部会议所需的时长 $t_i$。
输出格式
- 输出一个整数，表示在安全时段内最多能召开的会议场数。
样例 1
输入 (Input)
6 20 5 4 2 3 6 7
输出 (Output)
3
样例说明
- **样例说明**：
安全时段为 6 点到 20 点，总可用时长为 $20 - 6 = 14$ 小时。
各分部需求时长分别为：`4, 2, 3, 6, 7`。
- 为了开更多的会，哈利优先选择时长短的会议：$2 + 3 + 4 = 9$ 小时（共 3 场）。
- 如果尝试再加一场时长为 6 的会议，总时长将达到 15 小时，超过了 14 小时的限制。
- 因此，最多只能开成 3 场会议。
- $0 \lt S, E, n \le 24$。
这是一个典型的**贪心算法**问题。在总时间配额固定的情况下，为了最大化完成的任务数量，应当优先选择消耗资源（时间）最少的任务。
1. 计算总安全时长 $T = E - S$。
2. 将所有会议时长按从小到大排序。
3. 依次累加时长，直到总和超过 $T$ 为止。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功