Book Allocation Problem
书架上的书按固定顺序排列，pages[i] 表示第 i 本书的页数。把这些书分给 students 个学生：每个学生都要拿到一段连续相邻的书，每人至少一本，而且每本书都必须恰好分给一名学生。学生的负担是他拿到的书的总页数。
返回最重负担的可能最小值。如果学生人数多于书的数量，返回 -1。
函数
- pagesinteger-array
- 每本书的页数，按书架顺序排列
- studentsinteger
- 共享这些书的学生人数
- 返回值integer
- 尽可能小的最大负载；如果学生人数多于书本数量，则为 -1
约束条件
1 ≤ pages.length ≤ 50001 ≤ pages[i] ≤ 1051 ≤ students ≤ 104- 当
students > pages.length时返回-1。
示例
- 输入
- pages = [25, 40, 15, 30, 50]students = 3
- 输出
- 65
- 解释
- 分发
[25, 40]、[15, 30]和[50]：负载分别为 65、45 和 50。限额为 64 时会失败：分发结果是[25]、[40, 15]、[30]、[50]，共 4 名学生。
- 输入
- pages = [10, 20]students = 3
- 输出
- -1
- 解释
- 两本书无法让三名学生每人分到一本，所以答案是
-1。
- 输入
- pages = [7, 3, 9]students = 3
- 输出
- 9
- 解释
- 三本书和三名学生，每名学生拿一本书。最重的是 9 页的书。
进阶
证明向上取整后的平均份额加上最厚的书，始终是一个可行的上限。在一排薄书中，这个上限能减少多少次检查？
提示
逐个打开提示，每个都会多透露一点。
不要寻找最佳切法，而是选定一个页面上限。如果每个人携带的页面都不能超过这个上限，你需要多少名学生？
按书架顺序分发书籍，只有当下一本书会超过限制时，才转给下一位学生。限制越高，需要的学生人数不会更多。
当学生人数多于书本数量时，返回
-1。否则，从最厚书本的厚度和平均份额中较大的那个值开始，到总量为止，对这个上限进行二分查找。
题解
切分书架的方式太多，但测试一个页面限制的成本很低：按书架顺序分发书籍，当某本书会超出限制时，就交给下一位学生，然后统计学生人数。限制越高，需要的学生人数就越少，因此符合条件的限制连成一段，二分查找就能找到这段的起点。
每次将页面限制提高一页
结果正确，但无法在最大的测试中运行完毕
思路
从 L = max(pages) 开始，因为有人要搬最厚的书，然后每次将 L 增加 1 页，直到贪心计数符合 students。所有更小的上限都不符合要求，因此第一个符合要求的上限就是答案。在第一个示例中，从 50 到 64 的每个上限都需要 4 个学生，而 65 需要 3 个学生：共检查 16 次。
答案可能是整架书：1 个学生搬运 5000 本每本有 10^5 页的书，意味着大约有 5 × 10^8 个上限，每个上限都要遍历 5000 本书。在时间列中，A 是答案，m 是最厚的书。
算法
- 如果
students > pages.length，返回-1。 - 写出上限为
L时的贪心计数：先设置一名学生，负载为 0；当load + pages[i] > L时，增加一名学生，并将负载设为pages[i]，否则将这本书的页数加到负载中。 - 将
L设为页数最多的书的页数。 - 当
L对应的学生人数超过students时，将L加 1。 - 返回
L。
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
limit = max(pages) # the thickest book has to fit somewhere
while studentsNeeded(pages, limit) > students:
limit += 1
return limit对页面限制进行二分查找
思路
贪心计数表示在上限为 L 时，任何分配方案所需的最少学生数。逐个学生与其他分配方案相比，每个贪心分配的学生只有在下一本书装不下时才会停止，因此他在书架上至少会往后分配到同样的位置。学生人数少于现有学生数也没关系：拿着两本书的学生可以把一本书交给没有书的学生，而且任何人的负载都不会增加。
因此，当贪心计数小于或等于 students 时，L 就可行。在 L 下可行的方案，在 L+1 下也可行，因此可以用二分查找找到第一个可行的上限。
搜索范围的下限取 max(pages) 和平均分配量 total / students 向上取整后的较大值，因为最大负载至少不小于这两者。上限是 total。在第一个示例中，范围是 54 到 160，搜索依次尝试 107、80、67、60、64、66 和 65。
算法
- 如果
students > pages.length，返回-1。 - 累加
total，并找出最厚的书。将lo设为最厚的书和(total + students - 1) / students中较大的值，并设置hi = total。 - 当
lo < hi时，取mid = lo + (hi - lo) / 2。 - 对
mid运行贪心计数。如果结果不超过students，则设置hi = mid；否则设置lo = mid + 1。 - 返回
lo。
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
total = sum(pages)
# no limit can be below the thickest book or below the average share
lo = max(max(pages), (total + students - 1) // students)
hi = total # one student could carry the whole shelf
while lo < hi:
mid = lo + (hi - lo) // 2
if studentsNeeded(pages, mid) <= students:
hi = mid # mid is enough, so the answer is mid or lower
else:
lo = mid + 1 # mid needs too many students
return lo
易错点和边界情况
- 跳过
-1检查。对于[10, 20]和 3 名学生，当上限为 20 时，贪心计数为 2，因此搜索会返回 20。 - 仅从平均分配值开始搜索范围。对于
[1, 9]和 2 名学生，平均值为 5，此时贪心算法会把 9 页的书单独分配，计数为 2，并返回 5。 - 检查是否恰好等于
students。对于[5, 5, 5, 5, 5, 5]和 4 名学生，答案是 10，此时贪心计数为 3。 - 对书本排序。
[10, 1, 1, 10]分给 2 名学生时，结果为 11，但排序为[1, 1, 10, 10]后，结果为 12。
常见问题3
书籍分配问题和拆分数组最大和问题是同一个问题吗？
是的。两者都会将数组分成固定数量的非空连续块，并使最大的块和最小化；两者都可以用相同的二分查找和相同的贪心检查来解决。书本版本还加入了 -1 的情况。
书籍分配问题的时间复杂度是多少？
时间复杂度为 O(n log S)，额外空间复杂度为 O(1)，其中 n 是书本数量，S 是总页数。每次尝试一个限制值，都要遍历一遍书本；搜索大约会尝试 log2 S 个限制值：对于一本总页数为 5 × 10^8 的书架，共尝试 29 个限制值。
什么时候无法分配这些书？
只有当学生人数多于书本数量时才会这样，因为每个学生至少需要一本书。书本足够时，任意一组两本或更多的书都可以把最后一本分给还没有书的学生，直到每个人都有一本书。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def allocateBooks(pages, students):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
pages = [25, 40, 15, 30, 50] students = 3
预期输出
65