6/20的每日
紀錄一下
1552. Magnetic Force Between Two Balls
有一個矩陣position，position[i]代表這個位置有桶子
每個桶子都可以放一顆球
請問兩顆球間距離最小值的最大值是多少
思路:
先將positons排序
接著用二分搜尋法去尋找最大可以放完所有球的距離
golang code :
func maxDistance(position []int, m int) int {
slices.Sort(position)
n := len(position)
chk := func(distance int) bool {
cnt, last := 1, position[0]
for i := 1; i < n; i++ {
if position[i]-last >= distance {
cnt++
last = position[i]
}
if cnt >= m {
return true
}
}
return false
}
l, r := 1, position[n-1]-position[0]+1
for r > l {
m := l + (r-l)/2
if chk(m) {
l = m + 1
} else {
r = m
}
}
return l - 1
}