书籍复印

https://www.lintcode.com/problem/437

给定n本书，第i本书有pages[i]页。有k个人来抄这些书。

这些书排成一行，每个人都可以索取连续一段的书。例如，一个抄书人可以连续地将书从第i册复制到第j册，但是他不能复制第1册、第2册和第4册（没有第3册）。

他们在同一时间开始抄书，每抄一页书都要花1分钟。为了让最慢的抄书人能在最早的时间完成书的分配，最好的策略是什么？

请返回最慢抄书人花费的最短时间。

书籍页数总和小于等于2147483647

样例

样例 1:

输入: pages = [3, 2, 4], k = 2输出: 5解释: 第一个人复印前两本书, 耗时 5 分钟. 第二个人复印第三本书, 耗时 4 分钟.

样例 2:

输入: pages = [3, 2, 4], k = 3输出: 4解释: 三个人各复印一本书.

挑战

时间复杂度 O(nk)

解题思路：

关键在于搞定如何获得给定时间限制内，最少需要多少个人来复印。

• 首先，给定的时间在max(pages)到sum(pages)之间。

• 其次，在max(pages)到sum(pages)之间进行二分。对于给定的limit（capacity），肯定是至少需要一个人来完成工作，因此person可以初始化为1。

• 然后，初始的复印数是0，每复印page页，check一下复印的总数目是否超过了limit，如果超过limit，那就要再加一个人来工作，person++。将累计复印的数目重置为0。继续循环。

• 最后返回结果是pages count，因为一页一分钟，所以也是时间数

from typing import (
    List,
)

class Solution:
    """
    @param pages: an array of integers
    @param k: An integer
    @return: an integer
    """
    def copy_books(self, pages: List[int], k: int) -> int:
        # write your code here
        if not pages:
            return 0
        max_pages = max(pages)
        sum_pages = sum(pages)
        s, e = max_pages, sum_pages
        while s + 1 < e:
            mid = (s+e)//2
            if(self.can_copy(pages, k, mid)):
                e = mid
            else:
                s = mid

        if(self.can_copy(pages, k, s)):
            return s
        return e




    def can_copy(self, pages: List[int], k: int, capacity: int) -> bool:
        total, worker = 0, 1

        for p in pages:
            if total + p > capacity: #打印任务 > 可负荷量，需要加人
                worker += 1
                total = 0
            total += p #不在else里 total无论如何每次都要更新
        
        return worker <= k