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

我的解法超出时间限制，即使这样还有很多问题：

1. spells[i] * potions[j]溢出，应该将其强制类型转换为long long类型。
2. 循环条件中如果使用for (auto i: spells)，不能使用ans[i]再存储count了

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        int n = spells.size(), m = potions.size();
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = m-1; j >= 0; j--) {
                if ((long long)spells[i] * potions[j] >= success) {
                    count++;
                } else {
                    break;
                }
            }
            ans[i] = count; 
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

正确解法：排序+二分查找
在原来的解法中，判断过于繁琐，可以采用二分查找来简化步骤。
可以参考2258. 逃离火灾中的二分查找。

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        int n = spells.size(), m = potions.size();
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            int left = 0, right = m - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if ((long long)spells[i] * potions[mid] < success) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            ans[i] = m - left;	// 注意这里返回的值
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21