切割木头

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param a int整型一维数组
# @param k int整型
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/707d98cee255448c838c76918a702be0?tpId=196&tqId=40513&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：山山ks
    算法：
        本题考查的是我们以长度m切割每根木头，判断是否能切割出大于等于k根长度为m的木头
        1. 对于m的选取，我们采用二分法，在区间[1, max(a)]中寻找
        2. 若切割之后，长度为m的木头数量小于k，说明m选大了，right = mid - 1；否则，我们缩小区间为[mid, right]。
    复杂度：
        时间复杂度：O(nlogn + nlogx)，n为a的长度，x为max(a)
        空间复杂度：O(n)
    """

    def cutWood(self, a, k):
        # write code here
        a.sort()

        left, right = 1, a[-1]
        n, m = len(a), 0
        while left < right:
            mid = left + (right - left + 1) / 2

            count = 0
            for i in range(n - 1, -1, -1):
                if a[i] < mid:
                    break
                count += a[i] / mid

            if count >= k:
                left = mid
            else:
                right = mid - 1

        return left


if __name__ == "__main__":
    sol = Solution()

    # a, k = [1, 2, 3, 4, 5], 3

    # a, k = [1, 2, 3, 4, 5], 5

    a, k = [1, 2, 3, 4, 5], 7

    res = sol.cutWood(a, k)

    print res