javascript - 如何解决编码minMaxDivision
问题描述
我一直在尝试解决 1H30 的这个 codility 问题,以及如何使用二进制搜索来解决。我找到了答案,但我无法理解其背后的逻辑。得到它的人可以引导我完成这个答案。
这是问题
任务描述
给定整数 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;
}
解决方案
这是解决方案的二进制搜索。对于每个候选解决方案,我们迭代整个数组一次,将数组块填充到块在超过候选之前可以达到的最大总和。如果总和无法实现,则尝试较小的总和是没有意义的,因此我们搜索更高可能候选者的空间。如果总和是可以实现的,我们会尝试较低候选人的空间,而我们可以。
推荐阅读
- ios - 检查本地 GATT Profile 中的现有服务
- python - 在 32x32 图像中使用 eli5 排列重要性
- python - 使用 pandas 数据框将 csv 表设置为字典
- javascript - 翻译 .map 中的元素
- sql-server - SSRS 订阅 - 通过电子邮件发送报告时出错
- tensorflow - 没有 trimaps 的 create_tf_record
- kubernetes - 设置关联规则时,权重如何影响 Pod 调度?
- flutter - Flutter:如何仅流式传输 Firestore 文档中的一个字段?
- active-directory - RabbitMQ LDAP 配置在组搜索时失败
- java - Java 正则表达式检测句子结尾但忽略(num)(句点),例如 15