Allocate Book

题目描述

N number of books are given. The ith book has Pi number of pages. You have to allocate books to M number of students so that maximum number of pages alloted to a student is minimum. A book will be allocated to exactly one student. Each student has to be allocated atl east one book.

NOTE: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order.

解题方法

Solution

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

        while start + 1 < end:
            mid = start + (end-start)/2
            num_student = self.getNumStu(A, mid)
            print mid
            print num_student
            print "-------"
            if num_student <= B:
                end = mid
            else:
                start = mid + 1
        if self.getNumStu(A, start) <= B:
            return start
        else:
            return end


    def getNumStu(self, A, max_page):
        cur_page = 0
        num_stu = 1
        for p in A:
            cur_page += p
            if cur_page > max_page:
                cur_page = p
                num_stu += 1
        return num_stu

Reference