【Leetcode Daily】2300咒语和药水的成功对数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给两个数组和一个目标值，求一个数组中的每个值，与另一数组每个值之积大于目标值的个数。

思路分享

• 先要对数组做排序，这要才能二分查找，然后对一个数组的每个值做一次二分查找，就确认了个数，毕竟是有序的，右侧之积都不满足的情况下，左侧之积必然不满足。

• 二分的基本思路可以看 【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置。

• 不过，灵神的题解通过引入上取整和下取整的转换简化了不等式的比较，但暂且不甚理解，先放这里，说不定之后突然明白了呢。

  https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/solutions/1595712/by-endlesscheng-1kbp/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<int> res(spells.size());
        sort(potions.begin(), potions.end());
        for (int i = 0; i < spells.size(); i++) {
            long long s = spells[i];
            int left = 0, right = potions.size();
            while(left < right) {
                int mid = left+(right-left)/2;
                if (s*potions[mid] < success) {
                    left = mid+1;
                }
                else {
                    right = mid;
                }
            }
            res[i] = potions.size()-left;
        }
        return res;
    }
};