7.1华为OD机试真题 新系统 - 收集灵草 (JavaPyCC++JsGo)

收集灵草

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

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

题目描述

在一个远古修士的洞穴中，探宝者发现了一排共N棵灵草，每棵灵草有一个灵力值A，灵力值可为正、负或零。

为避免灵草被探宝者一扫而空，远古修士设置了禁制，要求探宝者必须选择一段连续的灵草序列带回，且必须满足以下规则：

规则一：选中的连续序列中，灵力值为正的数量不少于K棵。

规则二：在满足规则一的前提下，探宝者还可以从选中序列中额外挑选最多M棵灵力值为负的灵草丢弃，以提升总收益。

求所有合法选择方案中，能够走灵草的灵力值总和的最大值。如果无法满足规则一，输出-1。

数据范围：

• 1 <= N <= 10^4
• 1 <= K <= N
• 0 <= M <= 5
• -10^9 <= A <= 10^9

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

输入描述

输入格式：

N,K,M,[a1,a2,a3,...,aN]

其中：

• N表示灵草数量
• K表示至少需要选择的正数灵草数量
• M表示最多可丢弃的负数灵草数量
• [a1,a2,...,aN]表示灵草灵力值数组

输出描述

输出一个整数，表示最大灵力值总和；若不存在满足条件的连续子序列，则输出-1。

示例1

输入

8323,-5,4,-1,2,-8,6,-2

输出

14

说明

• 选中序列[3,-5,4,-1,2,-8,6]（下标1~7），灵力值为正的灵草有3、4、2、6共4棵且>= K=3，满足规则一。
• 该序列总和= 3 + (-5) + 4 + (-1) + 2 + (-8) + 6 = 1。
• 丢弃最多M=2棵负灵力值灵草：选-8和-5丢弃，剩余总和= 1 - (-8) - (-5) = 14。

示例2

输入

541-1,-2,3,-4,5

输出

-1

说明

任意连续子序列中正灵力值灵草最多只有3棵（如[1,-2,3,-4,5]中正值为1、3、5），无法达到K=4。

解题思路

核心思想

双指针枚举区间 + 小顶堆维护最大M个负数绝对值： 1. 枚举所有可能的连续子数组 [l, r] 2. 维护当前区间的正数个数 3. 用小顶堆维护当前区间最大的 M 个负数的绝对值之和 4. 当正数个数 >= K 时，计算 cur_sum + neg_sum（丢弃负数后的实际收益）

算法步骤

1. 预处理：统计全局正数个数，如果不足 K 直接返回 -1
2. 外层循环枚举左端点 l
3. 内层循环枚举右端点 r，逐步扩展区间
4. 维护正数计数和负数小顶堆
5. 当正数个数 >= K 时，更新答案 ans = max(ans, cur_sum + neg_sum)

复杂度分析

• 时间复杂度：O(N²)，双指针遍历所有区间
• 空间复杂度：O(M)，堆的大小