分石子

分石子问题

题解源自：牛客大佬——745599318

思路：
#令res表示分裂后m堆的最小值，
#res一定在[1, min{a[i], i=0,1...,n-1}]区间内，记左右区间分别为left, right。
#mid初始值去区间中值，即mid=left+(right-left)/2，利用二分思想不断找到mid的最终值。
#因为要求最小值最大，所以分堆的时候会尽量使每一堆的数据尽量均匀且接近最小值mid，
#具体地，对于其中一对a[i]，在最小堆值为mid的条件下，最多可分为a[i]/mid堆。
#记所有堆可分别的堆数位cnt（a[0]/mid+....+a[n-1]/mid），
#若cnt<m，堆数不够，需减小mid，设右边界right=mid-1；
#若cnt>m，需增大mid，设左边界left=mid+1；
#若cnt==m，也不一定就是最终答案，因为mid稍微增大一点可能cnt的值并不会改变，还要继续向后找，left=mid+1.

class Solution:
    def solve(self , n , m , a ):
        if n == m: return min(a)
        left, right = 1, min(a)
        while left<right:
            mid = (left+right+1) >> 1  #二分法取mid值；
            total = sum(nums//mid for nums in a) #当mid为分m堆后的最小值时，共可以分total堆；
            if total >= m:
                left = mid  #当最小值为mid的时候，堆数大于等于m，说明mid可能最小值中的最大也可能不是，说不定mid也满足total = m；
            else:
                right = mid-1 #total小于m，说明mid大了，分得堆数小于m，需要减小m
        return left