2026 华为OD机试真题 6月22日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

在通信系统中，有一组数据包需要按顺序通过 k 个通道传输。每个数据包 i 的传输耗时为 nums[i]（单位：毫秒）。

2026 华为OD机试真题 6月22日华为OD上机新系统考试真题 200 分题型

传输规则

• 同一通道内的数据包必须按顺序连续传输，即若数据包 [i, i+1, ..., j] 分配给同一通道，则该通道的传输总延迟为 nums[i]+nums[i+1]+...+nums[j]。
• 不同通道之间可以并行传输，系统整体延迟取决于延迟最大的那个通道。
• 数据包只能被拆分为连续子段，例如 [1, 2, 3] 可以被拆分为 [1, 2], [3]，但是不能被拆分为 [1, 3], [2]。

你的任务是：将 nums 数组划分到 k 个连续非空通道，使得传输总耗时最小。

输入描述

• nums：非负整数数组，长度 n（1≤n≤1000），每个元素满足 0≤nums[j]≤106。
• k：整数，通道数量（1≤k≤n）。

输出描述

• 返回一个整数，值为符合题意的最优传输策略下的总耗时。

示例1

输入

7,2,5,10,8
2

输出

18

说明

输入: nums=[7, 2, 5, 10, 8], k=2 输出: 18 解释: 共有以下划分方案（划分为2个连续子数组）： 方案1: [7], [2,5,10,8]→ 总耗时为 25 方案2: [7,2], [5,10,8]→ 总耗时为 23 方案3: [7,2,5], [10,8]→ 总耗时为 18← 最优 方案4: [7,2,5,10], [8]→ 总耗时为 24 因此最优总耗时为 18。

示例2

输入

[1, 2, 3, 4, 5],2

输出

9

说明

输入: nums=[1, 2, 3, 4, 5], k=2 输出: 9 解释: 最优划分为 [1,2,3] 和 [4,5]，最优总耗时为 9。

示例3

输入

1, 4, 4
3

输出

4

说明

输入: nums=[1, 4, 4], k=3 输出: 4 解释: 划分为 [1], [4], [4]，最优总耗时为 4。

解题思路

本题要求将数组划分为 k 个连续非空子段，使得所有子段和的最大值最小。这是一个经典的「分割数组/划分问题」，常使用二分查找 + 贪心验证策略求解。

关键洞察：

• 如果某个阈值 limit 可行（能将数组划分为不超过 k 个子段，且每个子段和 ≤ limit），那么所有更大的阈值也一定可行。
• 如果某个阈值 limit 不可行，那么所有更小的阈值也一定不可行。
• 这种单调性使得我们可以使用二分查找找到最小的可行阈值。

算法流程：

1. 确定搜索范围：下界为数组中的最大值（每个数据包必须单独传输），上界为数组所有元素之和（所有数据包在一个通道）。
2. 二分查找：对于每个候选阈值 mid，使用贪心算法检查能否将数组划分为不超过 k 个子段。
3. 贪心验证：遍历数组，尽量在当前段中添加元素，如果添加后超过 mid，则开启新段。最终统计所需段数是否 ≤ k。

复杂度分析

• 时间复杂度：O(n × log(sum))，其中 n 是数组长度，sum 是数组元素之和。二分查找 log(sum) 次，每次验证 O(n)。
• 空间复杂度：O(1)，只使用了常数额外