企业官网建设流程全解析

目录

题目

思路

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)。

Code

import 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)

JS

const 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机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。