目录题目思路Code题目题目内容末世时代政府需要把资源分配表 nums 分给 k 个营地。每个营地只能得到一段连续资源每个营地至少得到一份资源并且所有资源必须全部分完。分配应尽量平均即让获得资源总值最大的营地所获资源尽可能小。请返回这个最小可能的最大资源总值。输入描述输入共两行。第一行是英文逗号分隔的正整数数组 nums数组长度 n 满足 1 n 10000每份资源值满足 1 nums[i] 100000。第二行是营地数 k满足 1 k min(50,n)。输出描述输出最优分配方案中的最大连续段和。样例 1输入4,3,6,9,7 2输出16说明切分为 [4,3,6] 和 [9,7] 时两段最大值为 16且不存在更小的可行最大值。思路整体思路答案具有单调性可以二分最大段和并用贪心判断候选上限是否可行。第一步答案下界是数组最大元素上界是所有元素之和。第二步给定上限 mid从左到右尽量把资源放进当前段超出 mid 时开启新段。第三步若需要的最少段数不超过 k则正整数数组还能继续拆分为恰好 k 段mid 可行。边界处理k 等于 1 时答案为总和k 等于 n 时答案为最大元素。复杂度分析时间复杂度 O(N log S)S 为数组总和额外空间复杂度 O(1)。Codeimport re import sys lines sys.stdin.read().strip().splitlines() nums list(map(int, re.findall(r\d, lines[0]))) k int(lines[1]) # 最大段和至少容纳最大的单份资源至多等于所有资源放入一个营地的总和。 left, right max(nums), sum(nums) # 二分区间始终包含最小可行上限左右重合时即得到该上限。 while left right: middle (left right) // 2 # groups 是限制每段不超过 middle 时所需的最少段数current 是当前段之和。 groups 1 current 0 # 每段都尽量向右延伸正数条件保证这种贪心不会比其他切法使用更多空间。 for value in nums: # 若继续放入当前段会超限任何合法方案都必须在当前资源之前切开。 if current value middle: groups 1 current value else: current value # 最少段数不超过 k 时可继续拆分正数段直至恰好 k 段因此 middle 可行。 if groups k: right middle else: # 需要超过 k 段说明上限过小所有不大于 middle 的候选都可排除。 left middle 1 print(left)JSconst fs require(fs); const lines fs.readFileSync(0, utf8).trim().split(/\r?\n/); // 资源数组以逗号分隔只需按原顺序提取其中的正整数。 const nums [...lines[0].matchAll(/\d/g)].map((item) Number(item[0])); const k Number(lines[1]); // 最大段和至少容纳最大的单份资源至多等于全部资源之和。 let left Math.max(...nums); let right nums.reduce((sum, value) sum value, 0); // [left, right] 始终包含最小可行上限左右重合时即得到答案。 while (left right) { const middle Math.floor(left (right - left) / 2); // groups 是限制每段不超过 middle 时所需的最少段数。 let groups 1; // current 保存尚未封口的当前连续段之和。 let current 0; // 每段尽量向右延伸正数条件保证超限前不必提前切分。 for (const value of nums) { // 加入当前资源会超限任何合法方案都必须在它之前切开。 if (current value middle) { groups; current value; } else { current value; } } // 最少段数不超过 k 时可继续拆分正数段直至恰好 k 段。 if (groups k) { right middle; } else { // middle 过小连同所有更小候选一起排除。 left middle 1; } } console.log(left);【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。