算法题 — 可可喜欢吃香蕉(二分查找法)

可可喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开，将在 H 小时后回来。

可可可以决定它吃香蕉的速度为 speed (单位：根/小时)。每个小时，可可都会选择一堆香蕉，并吃掉 speed 根。如果这堆香蕉少于 K 根，可可就会吃掉这堆里所有的香蕉，然后，在这一小时内不会吃更多的香蕉。

可可想要在警卫回来之前吃掉所有的香蕉。

示例：

输入：piles = [3, 6, 7, 11]，h = 8，输出：4

输入：piles = [30, 11, 23, 4, 20]，h = 5，输出：30

输入：piles = [30, 11, 23, 4, 20]，h = 6，输出：23

fun main() {
    val piles1 = arrayOf(3, 6, 7, 11)
    val piles2 = arrayOf(30, 11, 23, 4,20)

	getMinSeed(piles1, 8)
  	getMinSeed(piles2, 5)
  	getMinSeed(piles2, 6)
}

fun getMinSeed(piles: Array<Int>, h: Int): Int {
    var left = 1 // 最小的速度
    var right = getMaxNum(piles)  // 最大速度，最大速度是数组中最大的的元素数量

    while (left < right) {
        val mid = left + (right - left) / 2
        if (canFinish(piles, mid, h)) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

/**
 * 按照当前的速度是否可以吃完香蕉
 */
fun canFinish(piles: Array<Int>, speed: Int, h: Int): Boolean {
    var t = 0 // 按照当前的速度，吃完所有的香蕉所需要的时间
    for (num in piles) {
        if (num % speed != 0) {
            t++
        }
        t += num / speed
    }
    return t <= h
}

/**
 * 获取数组中的最大值
 */
fun getMaxNum(piles: Array<Int>): Int {
    var max = 0
    for (n in piles) {
        // 获取 piles 数组中最大的元素值
        max = n.coerceAtLeast(max)
    }
    return max
}