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

Question

输入是一个由正整数或空整数组成的数组 A 和另一个整数 K。

我们应该将 A 分成 K 个连续元素 block (“分区”是指 A 的每个元素都属于某个 block ，并且 2 个不同的 block 不包含任何共同元素)。

我们将 block 的总和定义为 block 中元素的总和。

目标是在 K 个 block 中找到这样的分区，使得每个 block 的总和的最大值(我们称之为“MaxSumBlock”)最小化。

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

这是一个例子:

输入:

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

预期输出:

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

在预期的输出中，每个 block 的总和为3、6和6。最大值为6。

这是一个非最优划分:

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

在这种情况下，每个 block 的总和为 3、6 和 7。因此最大值为 7。这不是正确答案。

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

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

Answer 1

使用二进制搜索。

让最大和的范围从 0 到 sum(array)。所以，mid = (range/2)。看看是否可以在 O(n) 时间内通过划分成 k 集来实现 mid。如果是，则选择较低的范围，如果不是，则选择较高的范围。

这将为您提供 O(n log n) 的结果。

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

编辑:
根据要求，我将解释如何确定 mid 是否可以通过在 O(n) 时间内划分为 k 集来实现。
遍历元素直到总和小于或等于 mid。一旦它大于 mid，就让它成为下一组的一部分。如果你得到 k 或更少的集合，mid 是可以实现的，否则不是。