-2

在图书馆里有N书的页数由 给出。这些书将分配给学生,使得分配给任何学生的书的最大页数总和与最小页数总和之间的差值在分配给任何学生的书籍中,对于给定的输入是最小的。书籍也按一定的顺序排列,这个顺序永远不能改变。ib_iK

例如:

假设B[]包含每本书的页数。

然后对于N=6 K=3 B={3,7,8,2,6,4},输出将是0因为我们可以将书 1 和 2 给学生 1,将书 3 和 4 给学生 2,剩下的给学生 3。这使得学生 1 的 10 页 2 的 10 页和 3 的 10 页,因此差异为 0

同样,当B={3,6,8,2,6,4}最小差异为 1 时。

4

2 回答 2

0

这是一个贪婪O(nklogk)算法的想法,可以让你开始。首先,将书籍从大到小排序。然后取出最大的未分配的书并将其分配给总页数最少的孩子。继续这样做,直到所有的书都被分配。每本书的作业都要求您根据孩子的总页数对他们进行排序。

于 2012-06-14T18:29:20.730 回答
0

w=B 中页面的总和,您应该计算 w/n 以找到有限的答案。如果 w/n 是整数,这意味着您有这个问题。是否有 x 个元素的总和等于 w/n。这似乎NP问题

于 2012-06-14T18:35:41.570 回答