1552. 两球之间的磁力¶

难度：中等

题目¶

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。

给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。

示例 1：

输入：position = [1,2,3,4,7], m = 3

输出：3

解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。

示例 2：

输入：position = [5,4,3,2,1,1000000000], m = 2

输出：999999999

解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。

提示：

n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
所有 position 中的整数 互不相同 。
2 <= m <= position.length

Reference

题解¶

和1760. 袋子里最少数目的球的思路类似，对于一个最小磁力distance约束，如果我们能用x个小球满足该约束，则对于所有的小球数y > x，该约束同样可以被满足。反之，如果我们不能用x个小球满足该约束，对于所有的小球数y < x，该约束同样不可以被满足。因此，该distance数组（如果把满足该distance要求所需的小球数量存储为数组）满足单调递减的性质。可以使用二分查找的方式进行搜索，注意边界条件。

初始边界为\([lo, hi)\)，其中左边界[lo)为排序后position数组相邻元素的最小差值；右边界为position数组最大最小元素之差\(\color{red}+1\)（因为右边界为开）。
如果当前区间中点(lo + hi) >> 1所需球的数量不多于已有球的数量，则说明当前的距离偏小（或正合适），正确答案落在右半区间。
如果当前区间中点(lo + hi) >> 1所需球的数量多于已有球的数量，则说明当前的距离严格偏大，正确答案落在左半区间。

class Solution:
    def check(self, position: List[int], distance: int) -> int:
        last_pos = -distance
        result = 0
        for i in position:
            if i - last_pos >= distance:
                result += 1
                last_pos = i
        return result

    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        lo, hi = 1, position[-1] - position[0] + 1
        while lo < hi - 1:
            med = (lo + hi) >> 1
            numBalls = self.check(position, med)
            if numBalls < m:
                hi = med
            else:
                lo = med

        return lo

1552. 两球之间的磁力¶

题目¶

题解¶

评论