2300.咒语和药水的成功对数

​​题目来源：

        leetcode题目，网址：2300. 咒语和药水的成功对数 - 力扣（LeetCode）

解题思路：

       将 potions 数组排序后二分查找能够满足要求的最小值即可。

解题代码：

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

总结：

        注意边界条件。

        官方题解给出了两种 解法。第一种是二分。第二种双指针，是将两个数组都排序后使用双指针查找，然后再按原来的顺序输出。

        C++ upper_bound(begin,end,num) 从数组的begin 位置到 end-1 位置二分查找第一个大于num 的数字。

        C++ lower_bound(begin,end,num) 从数组的begin 位置到 end-1 位置二分查找第一个小于等于 num 的数字。