> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/l2er-fen-cha-zhao/shu-ji-fu-yin.md).

# 书籍复印

给定`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，因为一页一分钟，所以也是时间数

```python
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





```