💻 魔理沙的魔导书收纳
华为 · 贪心 · 算法编程题
华为
贪心
n ≤ 100
时限 1 秒 / 256 MB
题目描述
雾雨魔理沙正在帕秋莉的图书馆中“借”阅魔导书。魔理沙初始拥有 E 点魔力值，她面前依次排列着 n 本被魔法结界保护的魔导书。
对于第 i 本魔导书，魔理沙可以选择挑战结界或直接跳过。
1. 挑战结界：只有当魔理沙当前的魔力值严格大于该结界消耗值 a_i 时，才能挑战成功。挑战成功后，她的魔力值会减少 a_i ，但随后会从魔导书中吸收 b_i 点魔力反馈。即：魔力值变为 current - a_i + b_i 。
2. 跳过：魔理沙不挑战该结界，直接前往下一本书，魔力值保持不变。
魔理沙希望在保证挑战过程中魔力值始终不为负数的情况下，尽可能多地收纳魔导书。请你计算她最多能成功挑战多少个结界。
输入输出
输入描述
第一行输入一个整数 E ( 1 ≤ E ≤ 10^9 )，代表魔理沙的初始魔力值。
第二行输入若干个由空格分隔的整数 a_i ( 1 ≤ a_i ≤ 10^9 )，代表每本魔导书的结界消耗值。
第三行输入若干个由空格分隔的整数 b_i ( 1 ≤ b_i ≤ 10^9 )，代表挑战成功后的魔力反馈值。
两行数组的元素个数相同，设其长度为 n ( 1 ≤ n ≤ 100 )。
输出描述
输出一个整数，表示魔理沙最多能成功挑战的结界数量。
样例共 1 组
样例 1 · - 魔理沙初始魔力为 18 。
- 跳过第 1 本书（消耗 15，反馈 1），魔力仍为 18 。
- 挑战第 2 本书：当前魔力 18 > 17 ，挑战成功。魔力变为 18 - 17 + 15 = 16 。
- 挑战第 3 本书：当前魔力 16 > 4 ，挑战成功。魔力变为 16 - 4 + 4 = 16 。
- 第 4 本书消耗为 18 ，当前魔力 16 ≤ 18 ，无法挑战，只能跳过。
- 最终成功挑战的数量为 2。其他方案均无法超过 2。
输入
18
15 17 4 18
1 15 4 17
算法解析依据一般
考点：贪心
数据规模 n ≤ 100 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
题目画像
- 数据规模：n ≤ 100
- 元素值域：E ≤ 1e9，a_i ≤ 1e9，b_i ≤ 1e9（注意整数类型选择，避免溢出）
- 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
- 源站时限：1 秒（牛客口径，非本题专属门槛）
解题思路
参考方向：贪心
每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。
思路框架（贪心 通法 · 非本题专属）
- 找出「局部最优怎么选」（往往与排序后的顺序有关）。
- 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
- 按策略一次扫描（通常要先排序）得到答案。
- 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。
实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。
复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)
该范式的通法易错点
- 策略不成立却当成贪心做（典型错因）。
- 排序关键字选错，或相同关键字时的次级规则没考虑。
对照本题
- 数据规模 n ≤ 100，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
- 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例解读
样例 1：输入 18 / 15 17 4 18 / 1 15 4 17 → 输出 2
- 魔理沙初始魔力为 18 。
- 跳过第 1 本书（消耗 15，反馈 1），魔力仍为 18 。
- 挑战第 2 本书：当前魔力 18 > 17 ，挑战成功。魔力变为 18 - 17 + 15 = 16 。
- 挑战第 3 本书：当前魔力 16 > 4 ，挑战成功。魔力变为 16 - 4 + 4 = 16 。
- 第 4 本书消耗为 18 ，当前魔力 16 ≤ 18 ，无法挑战，只能跳过。
- 最终成功挑战的数量为 2。其他方案均无法超过 2。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解