咒语和药水的成功对数 图解题解
这道题到底在问什么
- 输入
- spells=[5,1,3], potions=[1,4,2,5,3], success=7
- 输出
- [4,0,3]
- 输入
- spells=[3,1,2], potions=[8,5,8], success=16
- 输出
- [2,0,2]
最优解：一步一步想明白
- 3记住「药水排序 → 每个咒语算 need=⌈success/s⌉ → 二分第一个 ≥ need 的位置 j → 成功数 = m − j」,下面每帧都在套它。
- 4第一步排序。原始药水是 [1, 4, 2, 5, 3],排好序变成 [1, 2, 3, 4, 5]。排序是后面二分的前提:有了从小到大的顺序,「第一个 ≥ need 的位置」之后的药水就全部达标。
- 5轮到第 1 个咒语,强度 s=5。要让 5·p ≥ 7,药水至少要 p ≥ ⌈7/5⌉ = 2。接下来在排好序的药水里二分找第一个 ≥ 2 的位置。
- 6当前搜索区间 [0, 5) 的中点是 potions[2]=3。它已经 ≥ need 2,说明第一个达标位就在它或它左边,把右边界收到 2。
- 7区间收窄到 [0, 2),继续二分。
- 8当前搜索区间 [0, 2) 的中点是 potions[1]=2。它已经 ≥ need 2,说明第一个达标位就在它或它左边,把右边界收到 1。
- 9区间收窄到 [0, 1),继续二分。
- 10当前搜索区间 [0, 1) 的中点是 potions[0]=1。它还小于 need 2,它和它左边都不够,把左边界推到 1。
- 11区间收空,二分结束:第一个 ≥ 2 的位置 j = 1。
- 12第一个 ≥ 2 的位置是 j=1。从 j 到末尾共 4 瓶药水(绿色)都满足 5·p ≥ 7,所以咒语 5 的成功数是 m − j = 4。答案接成 [4]。
- 13轮到第 2 个咒语,强度 s=1。要让 1·p ≥ 7,药水至少要 p ≥ ⌈7/1⌉ = 7。接下来在排好序的药水里二分找第一个 ≥ 7 的位置。
- 14当前搜索区间 [0, 5) 的中点是 potions[2]=3。它还小于 need 7,它和它左边都不够,把左边界推到 3。
- 15区间收窄到 [3, 5),继续二分。
- 16当前搜索区间 [3, 5) 的中点是 potions[4]=5。它还小于 need 7,它和它左边都不够,把左边界推到 5。
- 17区间收空,二分结束:第一个 ≥ 7 的位置 j = 5。
- 18第一个 ≥ 7 的位置是 j=5。从 j 到末尾共 0 瓶药水(绿色)都满足 1·p ≥ 7,所以咒语 1 的成功数是 m − j = 0。答案接成 [4, 0]。
- 19轮到第 3 个咒语,强度 s=3。要让 3·p ≥ 7,药水至少要 p ≥ ⌈7/3⌉ = 3。接下来在排好序的药水里二分找第一个 ≥ 3 的位置。
- 20当前搜索区间 [0, 5) 的中点是 potions[2]=3。它已经 ≥ need 3,说明第一个达标位就在它或它左边,把右边界收到 2。
- 21区间收窄到 [0, 2),继续二分。
- 22当前搜索区间 [0, 2) 的中点是 potions[1]=2。它还小于 need 3,它和它左边都不够,把左边界推到 2。
- 23区间收空,二分结束:第一个 ≥ 3 的位置 j = 2。
- 24第一个 ≥ 3 的位置是 j=2。从 j 到末尾共 3 瓶药水(绿色)都满足 3·p ≥ 7,所以咒语 3 的成功数是 m − j = 3。答案接成 [4, 0, 3]。
- 25三个咒语都算完了,成功数依次是 4、0、3,答案就是 [4, 0, 3],和开头说的一致。回头看:药水只排一次序,之后每个咒语都把「数有多少瓶达标」用一次二分 O(log m) 解决,不用逐瓶相乘。
⚠️ 容易写错的地方
✗ 错：用 success/s 浮点比较
✓ 对：need = (success+s−1)//s 整数向上取整
浮点有精度误差;向上取整保证 p ≥ need 严格等价于 s·p ≥ success
✗ 错：不排序直接二分
✓ 对：先把 potions 排序
二分依赖有序;不排序「第一个 ≥ need 之后全达标」不成立
✗ 错：成功数算成 j
✓ 对：成功数 = m − j
j 是第一个达标位,达标的是 j 到末尾这段,共 m − j 个
完整代码（Python / C++ / Java）
Python
from typing import List
from bisect import bisect_left
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
potions.sort()
m = len(potions)
ans = []
for s in spells:
need = (success + s - 1) // s
ans.append(m - bisect_left(potions, need))
return ansC++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
sort(potions.begin(), potions.end());
int m = potions.size();
vector<int> ans;
for (int s : spells) {
long long need = (success + s - 1) / s;
ans.push_back(m - (lower_bound(potions.begin(), potions.end(), need) - potions.begin()));
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
Arrays.sort(potions);
int[] ans = new int[spells.length];
int m = potions.length;
for (int i = 0; i < spells.length; i++) {
long need = (success + spells[i] - 1) / spells[i];
int l = 0, r = m;
while (l < r) {
int mid = (l + r) / 2;
if (potions[mid] >= need) r = mid;
else l = mid + 1;
}
ans[i] = m - l;
}
return ans;
}
}复杂度
时间
O((n + m) log m)
排序药水 O(m log m);n 个咒语每个二分一次各 O(log m),合计 O(n log m)
空间
O(1)
除排序与返回数组外,只用 need、二分指针几个变量;排序栈空间另算
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 咒语和药水的成功对数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不排序、用别的办法?+
可以先统计药水的桶/前缀和,但通用且好写的就是「排序 + 二分」:排序一次,每个咒语 O(log m) 查「有多少药水 ≥ need」。这也是「对一个数组排序后,用二分快速回答多次区间计数查询」的经典套路。
为什么二分找的是「第一个 ≥ need」?+
排序后,达标的药水(p ≥ need)一定是连续的一段后缀。找到这段的起点 j(第一个 ≥ need 的位置),后缀长度 m − j 就是成功数,一次二分搞定。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 咒语和药水的成功对数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。