※ 引述《Rushia (みけねこ的鼻屎)》之铭言:
: 2300. Successful Pairs of Spells and Potions
: 给定两个阵列spells和points,前者表示多个咒语的强度,后者表示多个药剂的强度,若
: 咒语和药剂相乘大于success则这一组咒语和药剂配对成功,返回一个长度为spells的阵列
: pairs,其中 pairs[i] 是能与第 i 个咒语配对成功的药剂数量。
: Example:
: Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
: Output: [4,0,3]
: Explanation:
: - 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
: - 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
: - 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
: Thus, [4,0,3] is returned.
: 思路:
: 1.最简单的方法就是两个阵列相互配对并计算数量,但是咒语和药剂的长度很大这样做
: 肯定会吃TLE。
: 2.我们可以先把药剂的强度排序好,每个咒语使用二分搜索找到最小且满足success的
: 药剂,这样这个索引的右边全部都是配对成功的药剂,若potions.length = n
: 满足数量就会是 n - index,如果最右边(最大)的药剂和咒语不满足则二分搜索直接
: 返回n不用继续找寻。
: Java Code:
: