二分查找（九）2300. 咒语和药水的成功对数
2300. 咒语和药水的成功对数
给你两个正整数数组
spells和potions，长度分别为n和m，其中spells[i]表示第i个咒语的能量强度，potions[j]表示第j瓶药水的能量强度。同时给你一个整数
success。一个咒语和药水的能量强度相乘如果大于等于success，那么它们视为一对成功的组合。请你返回一个长度为
n的整数数组pairs，其中pairs[i]是能跟第i个咒语成功组合的药水数目。示例 1：
输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7输出：[4,0,3]解释：- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。 - 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。 - 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。 所以返回 [4,0,3] 。
整体思路较为清楚，遍历每一份spells，利用这个spell来进行与potions每个元素乘积结果的判断，使用二分搜索优化，找到第一个大于等于target的位置，后续直接用个数-位置即可
class Solution { public: int lower_bound(int spell, vector<int>& potions, long long target) { int left = 0, right = potions.size()-1; while(left <= right) { int mid = left + (right-left)/2; // long long temp = potions[mid] * spell; // if(potions[mid] < target/spell) if (1LL * potions[mid] * spell < target) left = mid + 1; else right = mid - 1; } return left; } vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) { int n = spells.size(), m = potions.size(); vector<int> res(n); sort(potions.begin(), potions.end()); for(int i = 0; i < n; i++) { int index = lower_bound(spells[i], potions, success); res[i] = m - index; } return res; } };主要问题是记录一下long long型元素的结果溢出
以下错误写法：由于potions和spell元素都是int类型，所以他们会先进行相乘，但结果已经超过他们的存储范围了，这时候再用longlong来接收就已经晚了
方案A：使用1LL
long long temp = 1LL * potions[mid] * spell;
方案B：使用显示类型转换
long long temp =static_cast<long long>(potions[mid]) * spell;
int lower_bound(int spell, vector<int>& potions, long long target) { int left = 0, right = potions.size()-1; while(left <= right) { int mid = left + (right-left)/2; long long temp = potions[mid] * spell; if (potions[mid] * spell < target) left = mid + 1; else right = mid - 1; } return left; }还有就是把乘法转化为除法的形式：