Painter's partition problem

题目描述

ou have to paint N boards of length {A0, A1, A2, A3 … AN-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint contiguous sections of board.

解题方法

Solution

class Solution:
    # @param A : integer
    # @param B : integer
    # @param C : list of integers
    # @return an integer
    def paint(self, A, B, C):
        start = max(C)
        end = sum(C)

        while start + 1 < end:
            mid = start + (end-start)/2
            required_num = self.getRequiredPainters(C, mid)
            if required_num <= A:
                end = mid
            else:
                start = mid + 1
        if self.getRequiredPainters(C, start) <= A:
            return B * start
        else:
            return B * end

    def getRequiredPainters(self, l, max_per_painter):
        cur_total = 0
        num_painter = 1
        for i in range(len(l)):
            cur_total += l[i]
            if cur_total > max_per_painter:
                cur_total = l[i]
                num_painter += 1
        return num_painter

Reference