bih*_*ris 6 javascript algorithm binary-search-tree
我一直在努力解决这个 1H30 的问题，以及如何用二分搜索来解决。我找到了答案，但我无法理解其背后的逻辑。得到它的人可以引导我完成这个答案吗？
这是问题
任务描述
给定整数 K、M 和一个由 N 个整数组成的非空零索引数组 A。数组的每个元素都不大于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 和由 N 个整数组成的非空零索引数组 A，返回最小大和。
例如，给定 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..10,000]范围内的整数；数组 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;
}
我想更详细地解释我已经实现的算法，然后是 C++ 中的一个正确实现。
查找输入数组中的最大元素。我们也可以使用M，但M不一定会出现。较小的数字可能是最大值，因此这是轻微的优化。
计算输入数组的总和。这将是最大的总和。
应用二分查找，其中开始是最大元素，结束是总和。最小最大总和将在此范围内。
对于每次试验，检查我们是否可以将元素压缩到比请求的块数更少的块中。如果更少，也没关系，因为我们可以使用空块。如果相等的话也是可以接受的。然而，如果它更大，那么我们可以得出结论，尝试的最小最大和需要更高，以允许单个块更大，以减少块数。
上面可以观察到一个一般原则，即我们越公平地分配块的总和，最大的将成为可能的最小。为此，我们需要将尽可能多的元素压缩到一个单独的块中。
如果尝试的最小最大和的块数小于预期的块数，那么我们可以尝试稍小的最小最大和，否则我们必须尝试更大一点，直到最终找到最佳数字。
就运行时复杂性而言，解决方案是O(n * log(N * M))因为二分搜索是对数的。最坏情况下，总和可能是最大元素 M 的 N 倍，这会导致N * M使用二分搜索将范围一分为二。内层迭代会遍历所有元素，所以是N次。因此，它O(N * log(N * M))相当于O(N * log(N + M)。
int check(vector<int>& A, int largest_sum)
{
int sum = 0;
int count = 0;
for (size_t i = 0; i < A.size(); ++i) {
const int e = A[i];
if ((sum + e) > largest_sum) { sum = 0; ++count; }
sum += e;
}
return count;
}
int solution(int K, int /*M*/, vector<int> &A)
{
int start = *max_element(A.begin(), A.end());
int end = accumulate(A.begin(), A.end(), 0);
while (start <= end) {
int mid = (start + end) / 2;
if (check(A, mid) < K) end = mid - 1;
else start = mid + 1;
}
return start;
}