Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.212.164 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718991420.A.808.html
推 sustainer123: 我還沒補前兩天的 哇哇嗚嗚嗚