如何解决编码最小最大分割问题

How to solve codility minMaxDivision(如何解决编码最小最大分割问题)

问题描述

我一直在试图理解1H30的编码问题，以及如何使用二进制搜索来解决这个问题。我找到了答案，但我不明白背后的逻辑。能请得到它的人给我讲解一下这个答案吗？

这就是问题

任务说明 您将获得整数K、M和一个非空的零索引数组A 由N个整数组成的。数组的每个元素都不大于 大于M 应将此数组分为K个连续元素块。 挡路的大小是0到N之间的任意整数。 该数组应该属于某个挡路。 挡路从X到Y的和等于A[X]+A[X+1]+…+A[Y]。 空挡路的总和等于0。

大和是任何挡路中的最大和。 例如，给定整数K=3、M=5和数组A 那个： A[0]=2 A[1]=1 A[2]=5 A[3]=1 A[4]=2 A[5]=2
a[6]=2

例如，该数组可以分为以下块：

[2，1，5，1，2，2，2]，[]，[]，大和为15；[2]，[1，5，1， 2]，[2，2]，大和为9；[2，1，5]，[]，[1，2，2，2] 大和为8；[2，1]，[5，1]，[2，2，2]，大和为6。

目标是将大笔金额最小化。在上面的示例中，6是 最小大额金额。

编写函数：

函数解(K，M，A)；

在给定整数K、M和非空零索引数组A的情况下 由N个整数组成，返回最小的大和。

例如，给定K=3、M=5且数组A使得：

A[0]=2 A[1]=1 A[2]=5 A[3]=1 A[4]=2 A[5]=2
a[6]=2

该函数应返回6，如上所述。

假设：

N和K是[1..100,000]范围内的整数； m是[0..10000]范围内的整数； 数组A的每个元素都是[0..M]范围内的整数。

这是我能弄到的答案

function solution(K, M, A) {
    var begin = A.reduce((a, v) => (a + v), 0)
    begin = parseInt((begin+K-1)/K, 10);
    var maxA = Math.max(A);
    if (maxA > begin) begin = maxA;

    var end = begin + M + 1;
    var res = 0;

    while(begin <= end) {
        var mid = (begin + end) / 2;
        var sum = 0;
        var block = 1;
        for (var ind in A) {
            var a = A[ind];
            sum += a;
            if (sum > mid) {
                ++block;
                if (block > K) break;
                sum = a;
            }
        }
        if (block > K) {
            begin = mid + 1;
        } else {
            res = mid;
            end = mid - 1;
        }
    }
    return res;
}

推荐答案

这是解决方案上的binary search。对于每个候选解，我们遍历整个数组一次，将数组块填充到挡路在超过候选解之前所能达到的最大和。如果总和不能达到，那么尝试一个较小的总和就没有意义，所以我们搜索可能较高的候选者的空间。如果总和是可以实现的，我们会尽可能地尝试较低的候选空间。

这篇关于如何解决编码最小最大分割问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！