你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

5920. 分配给商店的最多商品的最小值

2021-11-7 13:45:32

题目链接:力扣

思路:最小化分配的最大值,这种说法想到二分~~二分什么呢?直接二分答案即可。端点为 l = 0,r = 数组中的最大值。二分一个值,然后判断这个值:如果按照这个值分完还有剩余,也就是需要更多的商店来分,说明值太小了不符合题意,那就需要把这个值变大如果能分完,那就把这个值变小。这样不断进行二分,最终就会获得正确答案了~~

注意:当mid为0的时候就不需要再进行判断了,一定不行,多少商店都分不完~~~~~~。

我的 check 这个函数,貌似还能优化,不过我这样写也是ok的~~~

时间复杂度O(nlogn)

上代码:

class Solution {

    private fun check(mid: Int, n: Int, quantities: IntArray): Boolean {
        if (mid == 0) {
            return false
        }
        var nn = n
        for (i in quantities.indices) {
            var mVal = quantities[i]
            while (mVal > 0) {
                mVal -= mid
                nn--
            }
        }
        if (nn < 0) {
            return false
        }
        return true
    }

    fun minimizedMaximum(n: Int, quantities: IntArray): Int {
        var maxx = 0
        for (i in quantities.indices) {
            maxx = Math.max(maxx, quantities[i])
        }
        var l = 0
        var r = maxx
        var ans = 0
        while (l <= r) {
            val mid = (l + r) / 2
            if (check(mid, n, quantities)) {
                ans = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return ans
    }
}