27122: 两球之间的磁力

binary search/greedy, http://cs101.openjudge.cn/practice/27122/

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

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

示例 1：

输入

第一行是整数数组长度 n 和一个整数 m。第二行是一个整数数组。

输出

最大化的最小磁力。

样例输入

sample1 in:
5 3
1 2 3 4 7

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

样例输出

sample2 input:
6 2
5 4 3 2 1 1000000000

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

提示

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

来源：LeetCode 1552

python

n,m = map(int, input().split())
*position, = map(int, input().split())
position.sort()

def check(x):
    cnt, pre = 1, position[0]
    for i in range(1,n):
        if position[i] - pre >= x:
            cnt += 1
            pre = position[i]
    
    return cnt >= m

# https://github.com/python/cpython/blob/main/Lib/bisect.py
lo = 1
hi = position[-1] - position[0] + 1
ans = 1
while lo < hi:
    mid = (lo + hi) // 2
    if check(mid):     
        ans = mid       # 如果cnt==m, mid就是答案
        lo = mid + 1    
    else:
        hi = mid
print(ans)

27122: 两球之间的磁力 ​

27122: 两球之间的磁力