2300. Successful Pairs of Spells and Potions

📘 題目敘述

給你兩個正整數陣列 spells 和 potions，長度分別為 n 和 m，其中 spells[i] 代表第 i 個咒語的力量，potions[j] 代表第 j 個藥水的力量。

同時給你一個正整數 success。

如果 spells[i] * potions[j] >= success，則這一對 (i, j) 被稱為 successful pair。

請回傳一個長度為 n 的整數陣列 pairs，其中 pairs[i] 表示第 i 個咒語能形成的 successful pairs 數量。

條件限制

• n == spells.length
• m == potions.length
• 1 <= n, m <= 10^5
• 1 <= spells[i], potions[j] <= 10^5
• 1 <= success <= 10^10

🧠 解題思路

我先把 potions 排序，因為每個 spell 都要找「有多少 potions 乘起來會 >= success」，排序後就能用二分搜尋快速找到分界點。

對於一個 spell 力量 i，我要找最小的 potion 力量 p 使得 i * p >= success，等價於 p >= success / i。

但這裡是整數，我要的是最小整數 p，所以我用天花板除法：goal = ceil(success / i) = (success + i - 1) / i。

接著在排序後的 potions 裡，用 lower_bound 找第一個 >= goal 的位置 l。那麼從 l 到最後的所有 potions 都能成功，數量就是 n - l（這裡的 n 是 potions 的長度）。

我把每個 spell 的結果依序 push 進 ans 回傳。

所有變數

• n：potions 的長度
• ans：輸出陣列，ans[i] 代表第 i 個 spell 的 successful pairs 數量
• l：二分搜尋左界（包含）
• r：二分搜尋右界（不包含）
• goal：對某個 spell 來說，成功所需的最小 potion 力量（天花板除法算出）

🪜 主要流程步驟

1. 先排序 potions，讓之後可以二分找分界

我先 sort(potions.begin(), potions.end())。排序後，potions 越後面越大，符合條件的會是後面一段連續區間。

2. 對每個 spell 計算 goal = ceil(success / spell)

對 spell 力量 i，我算 goal = (success + i - 1) / i，這代表想要讓 i * potion >= success，potion 至少要到多少。

3. 在 potions 裡找第一個 >= goal 的位置 l

我用二分搜尋在 [0, n) 找最小索引 l 使得 potions[l] >= goal。這個 l 就是成功區間的起點。

4. 成功的數量就是 n - l

因為 potions 已排序，從 l 到 n-1 都會成功，所以數量是 n - l，把它 push 到 ans。

5. 回傳 ans

所有 spells 做完後回傳 ans。

⏱️ 複雜度

• 時間複雜度：O(m log m + n log m)，m 是 potions 長度（排序），n 是 spells 長度（每個 spell 二分一次）。
• 空間複雜度：O(1)（不含輸出），主要是排序可能使用額外空間，ans 是輸出本身。

💻 程式碼實作

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n = potions.size();
        sort(potions.begin(), potions.end());
        vector<int> ans;
        for (int i : spells) {
            int l = 0, r = n; // 包含l不含r
            long long goal = (success + i - 1) / i;
            while (l < r) {
                int m = (l + r) / 2;
                if (potions[m] < goal) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            ans.push_back(n - l);
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/successful-pairs-of-spells-and-potions/