如何以最小化每个分区总和的最大值的方式对整数数组进行分区？

Question

输入是正整数或空整数的数组A和另一整数K.

我们应该将A分成K个连续元素块(通过"分区",我的意思是A的每个元素都属于某个块,而2个不同的块不包含任何共同的元素).

我们将块的总和定义为块的元素的总和.

目标是在K个块中找到这样的分区,使得每个块的最大值(让我们称之为" MaxSumBlock ")最小化.

我们需要输出MaxSumBlock(我们不需要找到实际的分区)

这是一个例子:

输入:

A = {2, 1, 5, 1, 2, 2, 2}
K = 3

预期产量:

MaxSumBlock: 6
(with partition: {2, 1}, {5, 1}, {2, 2, 2})

在预期输出中,每个块的总和为3,6和6.最大值为6.

这是一个非最佳分区:

partition: {2, 1}, {5}, {1, 2, 2, 2}

在这种情况下,每个块的总和是3,6和7.因此最大值是7.这不是正确的答案.

什么算法解决了这个问题？

编辑:K和A的大小不大于100'000.A的每个元素不大于10'000

Answer 1

使用二进制搜索.

设最大值的范围从0到sum(数组).所以,mid =(范围/ 2).通过k在O(n)时间内分组成组来查看是否可以实现mid .如果是,请选择较低的范围,如果不是,请选择更高的范围.

这将给出O(n log n)的结果.

PS:如果您在编写代码时遇到任何问题,我可以提供帮助,但我建议您先自己尝试一下.

编辑:
根据要求,我将解释如何mid通过k在O(n)时间内分割成集来实现.
迭代元素直到sum小于或等于mid.一旦它变大mid,就让它成为下一组的一部分.如果你得到k或更少的集合,mid是可以实现的,否则不是.