咒语和药水的成功对数

记住「药水排序 → 每个咒语算 need=⌈success/s⌉ → 二分第一个 ≥ need 的位置 j → 成功数 = m − j」,下面每帧都在套它。

第一步排序。原始药水是 [1, 4, 2, 5, 3],排好序变成 [1, 2, 3, 4, 5]。排序是后面二分的前提:有了从小到大的顺序,「第一个 ≥ need 的位置」之后的药水就全部达标。

轮到第 1 个咒语,强度 s=5。要让 5·p ≥ 7,药水至少要 p ≥ ⌈7/5⌉ = 2。接下来在排好序的药水里二分找第一个 ≥ 2 的位置。

当前搜索区间 [0, 5) 的中点是 potions[2]=3。它已经 ≥ need 2,说明第一个达标位就在它或它左边,把右边界收到 2。

区间收窄到 [0, 2),继续二分。

当前搜索区间 [0, 2) 的中点是 potions[1]=2。它已经 ≥ need 2,说明第一个达标位就在它或它左边,把右边界收到 1。

区间收窄到 [0, 1),继续二分。

当前搜索区间 [0, 1) 的中点是 potions[0]=1。它还小于 need 2,它和它左边都不够,把左边界推到 1。

区间收空,二分结束:第一个 ≥ 2 的位置 j = 1。

第一个 ≥ 2 的位置是 j=1。从 j 到末尾共 4 瓶药水(绿色)都满足 5·p ≥ 7,所以咒语 5 的成功数是 m − j = 4。答案接成 [4]。

轮到第 2 个咒语,强度 s=1。要让 1·p ≥ 7,药水至少要 p ≥ ⌈7/1⌉ = 7。接下来在排好序的药水里二分找第一个 ≥ 7 的位置。

当前搜索区间 [0, 5) 的中点是 potions[2]=3。它还小于 need 7,它和它左边都不够,把左边界推到 3。

区间收窄到 [3, 5),继续二分。

当前搜索区间 [3, 5) 的中点是 potions[4]=5。它还小于 need 7,它和它左边都不够,把左边界推到 5。

区间收空,二分结束:第一个 ≥ 7 的位置 j = 5。

第一个 ≥ 7 的位置是 j=5。从 j 到末尾共 0 瓶药水(绿色)都满足 1·p ≥ 7,所以咒语 1 的成功数是 m − j = 0。答案接成 [4, 0]。

轮到第 3 个咒语,强度 s=3。要让 3·p ≥ 7,药水至少要 p ≥ ⌈7/3⌉ = 3。接下来在排好序的药水里二分找第一个 ≥ 3 的位置。

当前搜索区间 [0, 5) 的中点是 potions[2]=3。它已经 ≥ need 3,说明第一个达标位就在它或它左边,把右边界收到 2。

区间收窄到 [0, 2),继续二分。

当前搜索区间 [0, 2) 的中点是 potions[1]=2。它还小于 need 3,它和它左边都不够,把左边界推到 2。

区间收空,二分结束:第一个 ≥ 3 的位置 j = 2。

第一个 ≥ 3 的位置是 j=2。从 j 到末尾共 3 瓶药水(绿色)都满足 3·p ≥ 7,所以咒语 3 的成功数是 m − j = 3。答案接成 [4, 0, 3]。

三个咒语都算完了,成功数依次是 4、0、3,答案就是 [4, 0, 3],和开头说的一致。回头看:药水只排一次序,之后每个咒语都把「数有多少瓶达标」用一次二分 O(log m) 解决,不用逐瓶相乘。

边界:咒语极强 need=1 时全成功;need 超过最大药水则 0。

面试点:排序 + 二分回答多次「≥ 某值的个数」,达标药水是连续后缀。