[左神面试]画匠问题：[贪心]

def solution(arr, num):  # 工作清单和工人数目 | O(N*logS), S=sum(arr)
    assert arr and len(arr) and num
    if len(arr) <= num:  # 如果工人过多，则是取最长的一个工作返回
        return max(arr)

    def get_need_num(limit):  # 每个画师只能工作不超过limit的时间，问需要几个画师才能完成
        res, worked = 1, 0  # 已用画师数目， 当前画师已工作时间
        for v in arr:
            if v > limit:  # 这一幅画哪怕单独分配给一个画师也完成不了
                return float('inf')
            worked += v
            if worked > limit:  # 如果尝试画当前的画已超工时
                res += 1  # 新增一个画师来画这幅画
                worked = v  # 新增画师的当前工时为v
        return res

    min_sum, max_sum = 0, sum(arr)  # 二分法确定每个画师的最大工作量
    while min_sum != max_sum - 1:
        mid = (min_sum + max_sum) // 2
        if get_need_num(mid) > num:
            min_sum = mid
        else:
            max_sum = mid
    return max_sum

n, num = map(int, input().split())
arrs = list(map(int, input().split()))
print(solution(arrs, num))