分配最少页数

问题陈述

您被给出大小为 N 的整数数组，其中表示 N 本书的页数。您还被给出一个整数 M，表示学生人数。您必须以某种方式将这 N 本书分配给 M 个学生阅读，以便每个学生都必须阅读一本书，并且所有书籍都应该被阅读。一个学生也可以阅读多本书，但书籍必须是连续的。书籍的顺序将按照页数升序排列。

您的任务是以某种方式将书籍分配给学生，使得分配给一名学生的页数最多应该尽可能少。

例如

令 N=5 且 M=3

Pages[] = { 120,132,165,324,987}

在上面的示例中，我们可以有以下可能性

情况 1

情况 3

情况 3

情况 4

情况 5

在这里，我们将使用二分查找来解决此问题。

这个问题有很多边界情况，例如

• 如果书的数量少于学生数量，则我们无法确定任何解决方案，并且将返回 -1。
• 如果书的数量等于学生数量，则答案将是数组中的最大值。
• 如果学生数量为 1，则数组的总和将是答案。

因此，我们知道，我们在有答案范围的地方应用二分查找。

在这个问题中，最小答案将是数组中的最大值，最大答案将是数组的总和。

Java 代码

输出

说明

在上面的代码中，我们实现了最小页数分配的二分查找解决方案。我们有包含五个值的页面数组，并且 m 等于 2。

对于二分查找，left = 987 且 right = sum (page) = 1728

mid= 987+(1728-987)/2 = 1357

现在，对于 mid 值，我们将检查是否可以以某种方式分配页面，使得分配给学生的页数最多小于 mid。

因此，我们将得到 true，现在我们的 left=987，right 将是 mid-1，即 1356。

现在 mid= 987+(1356-987)/2 = 1171

所以现在，对于 mid 值 1171，我们将从函数中得到 true，并将向左搜索空间移动。所以 right 现在将是 1170。

Mid = 987+(1170-987)/2 = 1078

所以现在对于 mid 值，我们将得到 true，我们将向左移动，所以 right=1077

Mid=987+(1077-987)/2 = 1032

所以我们将为 1032 得到 true，所以我们将再次向左，所以 right = 1031

Mid= 987+(1031-987)/2 = 1009

所以我们将再次得到 true，现在 right = 1008

而 mid= 987+(1008-987)/2 = 997

并且函数将返回 true 以 997，所以 right 将是 996。

Mid = 987+(996-987)/2 = 991

而且这也是 true，所以 right = 990

现在 mid = 987+(990-987)/2=988

再次，true，所以 right = 987

现在 mid =987，我们将得到 true，所以 right=986 但 left 987，所以循环将终止，mid =987 将保持为答案。

时间复杂度：O(logN)，其中 N 代表书中页的总数。

空间复杂度：O(1)