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

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

题目描述

某物流仓库有一个长度为 n 的货物处理队列，队列中的每个元素代表一个货物单元所需的处理时间（单位：分钟）。

管理员可以使用一种特殊的"处理优化"机制：每次优化操作可以选择一组连续的货物单元（注意：如果某个货物单元的处理时间为 0，则它两边的货物单元不视为连续），并将选中组内每个货物单元的处理时间减少 1 分钟。

给定一个货物处理队列 nums（表示各货物单元的处理时间）和一个整数 k（表示最多可进行的优化操作次数），你需要计算在不超过 k 次操作的情况下，仓库处理完所有货物的最短总处理时间。

关键规则说明

连续性的定义：

只有处理时间大于 0 的相邻货物单元才被视为连续。 如果遇到处理时间为 0 的货物单元，它会打断连续性。例如： 数组 [5,4,0,3] 被 0 分割为两个连续段：[5,4] 和 [3]。

操作规则： 每次操作只能选择一个连续段，并将段内所有货物单元的处理时间减 1。

操作后若某个货物单元的处理时间变为0，它可能会将原来的连续段分割为更小的段。

目标： 通过最多 k 次操作，使得最终所有货物单元的处理时间之和最小。

1 <= nums.length <= 10^5

0 <= nums[i] <= 10^5

0 <= k <= 10^5

输入描述

货物处理队列以及最多可进行的优化操作次数

输出描述

输出仓库处理完所有货物的最短总处理时间。

示例1

输入

[5,4,0,3],1

输出

10

说明

操作选择： 由于 0 的存在，连续段为 [5,4] 和 [3]。选择较长的段 [5,4] 进行优化（减 1），得到 [4,3,0,3]。

总时间：4 + 3 + 0 + 3 = 10

返回值：10

示例2

输入

[5,3,4],3

输出

3

说明

第一次操作：全段 [5,3,4] → [4,2,3]

第二次操作：全段 [4,2,3] → [3,1,2]

第三次操作：全段 [3,1,2] → [2,0,1]

总时间：2 + 0 + 1 = 3

返回值：3

解题思路

核心思想

本题的目标是在最多进行 $k$ 次操作（每次操作将一个不包含 0 的连续正数段的所有元素减 1）的情况下，使得数组的总和最小。等价于：每次操作最多可以减去该连续段的长度，我们需要在最多 $k$ 次操作中，最大化减去的总数值。

考虑到数组中数值较大的元素会存在于多个高度层中。我们可以将原问题转化为"从上到下逐层消除"的思路。使用并查集来动态维护连续段的合并与收益计算。

具体步骤如下：

1. 按高度分组：找到数组的最大值 max_value，将所有正数元素按照它们的值（高度）分配到对应的桶 by_height 中。
2. 从高到低扫描：
   • 从 max_value 向下遍历到 1。
   • 当扫描到高度 h 时，激活该高度层上的所有货物位置。
   • 使用并查集将新激活的位置与其左右相邻且已激活的位置合并。每次合并时，相当于旧的连续段在 [当前合并高度, 旧段起始高度) 这个区间内保持了固定的长度，因此结算这段高度差带来的收益（收益 = 段长度，频次 = 高度差）。
3. 结算剩余段：扫描到高度 0 时，结算所有仍处于独立状态的并查集根节点的剩余高度收益。
4. 贪心选择：
   • 经过上述过程，我们统计出了各种长度的连续段能够被操作的次数 count_by_len[length]。
   • 为了最大化减少的总处理时间，我们贪心地从最长的段开始选择操作。在允许的 $k$ 次操作内，优先消耗长度越长的连续段，将其长度累加到节省的总时间 saved 中。
5. 计算最终结果：最终答案 = 初始数组总和 - 最大节省时间 saved。

复杂度分析

• 时间复杂度：$O(N + M + \max(nums))$，其中 $N$ 是数组长度，$M$ 是并查集操作的次数。由于路径压缩的存在，并查集操作接近常数时间。整体时间复杂度线性相关于数组规模和最大值。
• 空间复杂度：$O(N + \max(nums))$，需要数组来存储每个高度的位置索引，以及并查集相关的 parent、size 等辅助数组。