**末世分配资源包**
2026 华为OD机试真题8月12日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
末世时代，政府为各地分配资源，现有资源分配表 nums[n]，要求按如下规则分配给 k 个营地：
- 每个营地只分配一段连续的分配表
- 每个营地至少分到一份资源
- 所有的资源必须全部分出
- 分配方式：尽量平均分配（即：得利最大的营地获得的资源值尽量小）
2026 华为OD机试真题8月12日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
输入描述
- 资源存储数组
nums[n]（资源数 n: 0≤n≤1000，每份资源数：1≤nums[i]≤100000） - 营地数 k（1≤k≤min(50,n)）
输入为两行：
nums
k其中 nums 为英文逗号分隔的整数数组。
输出描述
- 在最优平均分配情况下，得利最大团队所获得的资源数
示例1
输入
4,3,6,9,7
2输出
16说明
可能的切分：
[4],[3,6,9,7]，最大值：25[4,3],[6,9,7]，最大值：22[4,3,6],[9,7]，最大值：16[4,3,6,9],[7]，最大值：22因此，最大值最小的切分方式是第
3种，返回16
示例2
输入
3,4,2,1
4输出
4说明
可能的切分：
[3],[4],[2],[1]，最大值：4因此，最大值最小的切分方式是第
1种，返回4
解题思路
核心思想
题目要求把数组切成 k 段连续子数组，并让所有段中最大的段和尽可能小。
如果给定一个最大允许段和 limit，可以从左到右贪心分段：当前段能继续放就继续放，放不下就新开一段。这样得到的段数是该 limit 下所需的最少段数。
若最少段数 <= k，说明 limit 足够大，可以尝试更小的最大段和；否则说明 limit 太小，需要增大。
因此可以对答案做二分查找。
算法步骤
- 答案下界为
max(nums)，因为任何一段至少要容纳一个资源包。 - 答案上界为
sum(nums)，表示所有资源包分给一个营地。 - 二分枚举最大段和
mid。 - 使用贪心统计在每段和不超过
mid时，至少需要多少段。 - 如果段数
<= k，说明可行，缩小右边界；否则增大左边界。 - 二分结束后，
left即为最小可能的最大段和。
复杂度分析
设数组长度为 n，所有资源包总和为 S。
- 时间复杂度：
O(n log S) - 空间复杂度：`O
版权声明：
作者：魔改工程师
链接：https://www.sylblog.xin/archives/830
文章版权归作者所有，未经允许请勿转载。
THE END
