最佳阅读计划

Question

这是一道面试题，不是作业。

“Kindle 将实现一项新功能。功能：用户输入他希望完成某本书的天数，Kindle 将为用户创建阅读计划。 编写一个算法，将阅读计划输出给用户。在制定阅读计划时应牢记用户希望在同一天开始和结束阅读本书的特定“章节”。

现在，阅读计划必须是最优的，这可能意味着没有。字符或可能没有。每天要阅读的单词数量应尽可能公平地分布在不同的日子里。

现在，我们真的不知道 Kindle 如何在其后端存储这些书籍，但我认为可以安全地假设我们可以轻松获得以下数据--

1. 没有。本书章节数
2. 每一章的起点和终点
3. 没有。每章或每页的页数或字数或字符数等

我真的想不出具体的解决办法。有人请帮忙。

Answer 1

这可以看作是换行的一种变体。只有这里一个字是整章，行是天，你还不知道线宽（每天的字数）

它有一些非常不同的算法，从简单的 "fill each line as much as possible" 到动态规划和 SMAWK。

线宽可以单边二分查找，也可以先估计一下，应该接近total words / days（肯定不会小，希望不会大很多）

它不是 k-分区问题的一个变体，因为这些章节（大概）没有形成一个集合但是一个序列，必须按顺序阅读。因此，问题只是在该序列中插入中断，这要容易得多。