关于 Codility 的 MinMaxDivision 的解决方案的问题，它使用二进制搜索来解决它

Question

根据在线解决方案，我几乎想出了如何解决 Codility 的 MinMaxDivision，但解决方案中有一个细节我正在努力确认。

问题如下：

Task description

You are given integers K, M and a non-empty array A consisting of N integers. Every element of the array is not greater than M.

You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block.

The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.

The large sum is the maximal sum of any block.

For example, you are given integers K = 3, M = 5 and array A such that:
A[0] = 2
A[1] = 1
A[2] = 5
A[3] = 1
A[4] = 2
A[5] = 2  
A[6] = 2
The array can be divided, for example, into the following blocks:
[2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
[2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
[2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
[2, 1], [5, 1], [2, 2, 2] with a large sum of 6.
The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.

Write a function:
class Solution { public int solution(int K, int M, int[] A); }
that, given integers K, M and a non-empty array A consisting of N integers, returns the minimal large sum.

For example, given K = 3, M = 5 and array A such that:
A[0] = 2
A[1] = 1
A[2] = 5
A[3] = 1
A[4] = 2
A[5] = 2  
A[6] = 2
the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

N and K are integers within the range [1..100,000]; M is an integer

within the range [0..10,000]; each element of array A is an integer

within the range [0..M].

以下解决方案得到 100%:

public int solution(int K, int M, int[] A) {

    int min = 0;
    int max = 0;

    for (int i = 0; i < A.length; i++) {
        max += A[i];
        min = Math.max(min, A[i]);
    }

    if (K == 1)
        return max;

    if (K >= A.length)
        return min;

    int result = min;

    while (min <= max) {

        int mid = (min + max) / 2;

        if (check(mid, K, A)) {

            max = mid - 1;
            result = mid;

        } else {

            min = mid + 1;

        }

    }

    return result;
}

private boolean check(int mid, int k, int[] a) {

    int sum = 0;

    for (int i = 0; i < a.length; i++) {

        sum += a[i];

        if (sum > mid) {
            sum = a[i];
            k--;
        }

        if (k == 0)
            return false;

    }

    return true;

}

解的思路很简单：最小的大和在min(A)或sum(A)之间。我们可以使用二进制搜索来寻找最小的大和，而不是一个一个地迭代。对于每个候选者（mid），我们看看是否可以有 K 个不超过 mid 值的块。

我的问题是关于在上面的check()方法中根据中间值查找块数的策略。在某些情况下，块数符合标准，但 none 个块的总和等于中间值。 ~~一个很好的例子是当我们有一个包含所有数组值的块，而其他块是空的。~~

一个很好的例子是 A = [2, 3, 3, 5, 4, 2, 3], K = 3: 中间值最终得到值 10，我们可以有 3 个块 [2,3, 3],[5,4],[2,3] 但其中 none 等于 10.

求解算法是否可以输出一个中间值作为最小大和，但这个和实际上不存在？ check() 方法如何在不比较总和值与中间值的情况下始终找到最小大和并且该最小大和存在于数组中？

Answer 1

There are situations, where the number of blocks fits the criteria but none of the blocks have their sum equaling the mid value

这没关系，因为 check 将 return true 和较低的 mid 将被检查：一些较低的 mid 最终将被检查一个将等于某个块的总和。

One good example is A = [2, 3, 3, 5, 4, 2, 3], K = 3: the mid value eventually get's the value 10, we can have 3 blocks [2,3,3],[5,4],[2,3] but none of them are equal 10.

在 mid = 10 和 check returning true 之后，这将执行：

max = mid - 1;
result = mid;

通过将 max 设置为 9，9 最终也会被检查，并被 return 编辑。

Can the solution algorithm output a mid value being the minimum large sum but that sum actually does not exist?

不，因为如果那个总和不存在并且 check returns true，那么我们有一个可能的较小的总和 - 所以当前 mid不是最小值。如果算法得到 100%，那么它将输出这个较小的值。

同样根据问题陈述中给出的定义来思考：

The large sum is the maximal sum of any block.

[...]

The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.

因此，根据定义，最小大和是某个块的总和。

How can the check() method always find the minimum large sum, AND that minimum large sum exists in the array without comparing the sum value with the mid value?

check 方法本身不会找到最小大和。它只告诉你给定的总和（它的 mid 参数）是否有效（也就是说，如果我们可以将数组拆分为 K 最大总和的块<= mid).

二分查找求最小大和

关于 Codility 的 MinMaxDivision 的解决方案的问题，它使用二进制搜索来解决它

Question regarding the solution of Codility's MinMaxDivision, that uses binary search to solve it

java

algorithm

binary-search