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

本文介绍了如何解决编码最小最大分割问题的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我一直在试图理解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。对于每个候选解，我们遍历整个数组一次，将数组块填充到挡路在超过候选解之前所能达到的最大和。如果总和不能达到，那么尝试一个较小的总和就没有意义，所以我们搜索可能较高的候选者的空间。如果总和是可以实现的，我们会尽可能地尝试较低的候选空间。