【每日一题】咒语和药水的成功对数-CSDN博客

Tag

【排序+二分】【数组】【2023-11-10】

---

题目来源

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

---

解题思路

方法一排序+二分

我们首先对 points 进行升序排序然后枚举 spells 中的 x需要找到在 points 中大于等于 $\lceil \frac{success}{x}\rceil$ 的数量。那我们找到在 points 中大于等于 $\lceil \frac{success}{x}\rceil$ 最小位置 idx 即可这样在 points 中大于等于 $\lceil \frac{success}{x}\rceil$ 的数量就为 points.end() - idx。

为什么要找在 points 中大于等于 $\lceil \frac{success}{x}\rceil$ 的数量因为 x 和 points 中的 y某一瓶药水的能量强度要满足

$$xy>=success$$

找到满足上式的 y 的数量即为 x 对应的答案。上式即为 $x>=\lceil \frac{success}{x}\rceil$。

实现代码

class Solution {
public:
    vector<int> successfulPairs(vector<int> &spells, vector<int> &potions, long long success) {
        sort(potions.begin(), potions.end());
        for (int &x : spells) {
            long long target = (success + x - 1) / x;
            x = potions.end() - lower_bound(potions.begin(), potions.end(), target);
        }
        return spells;
    }
};

复杂度分析

时间复杂度$O(mlogm+nlogm)$$m$ 为数组 points 的长度$n$ 为数组 spells 的长度。

空间复杂度$O(logm)$。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。

如果大家有更优的时间、空间复杂度方法欢迎评论区交流。

最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。