如何划分的整数中最小化每个分区的总和的最大的方式的阵列？ [英] How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
问题描述
输入是积极的还是空整数数组A和另一个整数k。
The inputs are an array A of positive or null integers and another integer K.
我们应该划分成一个连续元素的K个块（由分区我的意思是A的每一个元素属于某些块和2个不同的块不包含任何共同的元素）。
We should partition A into K blocks of consecutive elements (by "partition" I mean that every element of A belongs to some block and 2 different blocks don't contain any element in common).
我们定义一个块的总和作为块的元素的和
We define the sum of a block as sum of the elements of the block.
的目标是找到在K个块这样的分区，使得每个块的和的最大值（让我们称之为的 MaxSumBlock 的）被最小化。
The goal is to find such a partition in K blocks such that the maximum of the sums of each block (let's call that "MaxSumBlock") is minimized.
我们需要输出MaxSumBlock（我们不需要找到一个实际的分区）
We need to output the MaxSumBlock (we don't need to find an actual partition)
下面是一个例子：
输入：
A = {2, 1, 5, 1, 2, 2, 2}
K = 3
期望的输出：
Expected output:
MaxSumBlock: 6
(with partition: {2, 1}, {5, 1}, {2, 2, 2})
在期望的输出，每个块的总和是3,6和6。max是6
In the expected output, the sums of each block are 3, 6 and 6. The max is 6.
下面是一个非最佳的分区：
Here is an non optimal partition:
partition: {2, 1}, {5}, {1, 2, 2, 2}
每个块的在这种情况下的总和是3，6和7的最大值是因此7.它不是一个正确的答案。
The sums of each block in that case are 3, 6 and 7. The max is hence 7. It is not a correct answer.
解决这个问题什么算法？
What algorithm solves this problem?
编辑：K和A的大小不大于100'000。 A的每个元素都是不超过10,000做大
K and the size of A is no bigger than 100'000. Each element of A is no bigger than 10'000
推荐答案
使用二进制搜索。
让最大一笔范围从0到总和（阵列）。因此，中=（范围/ 2）。看看中旬可以划分为O（n）时间来实现到 K 集。如果是的话，去为较低的范围内，如果没有，去一个更高的范围内。照片
Let max sum range from 0 to sum(array). So, mid = (range / 2). See if mid can be achieved by partitioning into k sets in O(n) time. If yes, go for lower range and if not, go for a higher range.
这会给你的结果为O（n log n）的。
This will give you the result in O(n log n).
PS：如果你有写code有什么问题，我可以帮助，但我建议你先自己尝试一下。
PS: if you have any problem with writing the code, I can help but I'd suggest you try it first yourself.
编辑：
根据要求，我将解释如何找到，如果中期可以通过分区来实现到 K 集为O（n ） 时间。
通过元素迭代，直到和小于或等于中期。一旦它得到大于中期，让它成为下一集的一部分。如果你得到 K 或更少套，中期是可以实现的，否则不行。
as requested, I'll explain how to find if mid can be achieved by partitioning into k sets in O(n) time.
Iterate through the elements till sum is less than or equal to mid. As soon as it gets greater than mid, let it be part of next set. If you get k or less sets, mid is achievable, else not.
这篇关于如何划分的整数中最小化每个分区的总和的最大的方式的阵列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
