华为 · 贪心 · 算法编程题
华为 贪心 N ≤ 200000 时限 1 秒 / 256 MB

题目描述

小红目前正在负责一家大型 AI 实验室的推理资源调度工作。为了提高大语言模型（LLM）的并行推理效率，她需要为当前任务队列中的一系列请求分配 Token 资源（单位：k）。
队列中的每个推理请求都有一个对应的优先级评分。在分配资源时，小红设定了如下调度规则：
1. 优先级评分小于或等于 0 的请求会被视为无效任务或系统预留任务，不参与本次 Token 分配，即分配到的 Token 数量为 0。
2. 这些无效任务会将整个请求序列切分成若干个由连续有效任务（优先级评分大于 0）构成的子段。
3. 对于每个有效任务子段，段内的每个请求至少要分配 1k 个 Token。
4. 在同一个子段内部，如果某个请求的优先级评分严格高于它左边或右边相邻的任务，那么它分配到的 Token 数量必须严格多于该相邻任务。
小红希望在完全满足上述规则的前提下，计算出分配给所有任务的 Token 总数最小值是多少。

输入输出

输入描述
输入包含一行，为若干个由英文逗号隔开的整数，代表任务队列中每个推理请求的优先级评分。
任务总数 N 满足 1 ≤ N ≤ 2 × 10^5 。
每个优先级评分 P_i 满足 -10^9 ≤ P_i ≤ 10^9 。
输出描述
输出一个整数，表示小红最少需要分配的 Token 总数（以 k 为单位）。

样例共 1 组

样例 1 · 在该样例中，优先级为 0 的任务将序列分割为两个有效子段：[3, 5, 2] 和 [8]。 - 对于子段 [3, 5, 2]，为了满足相邻优先级更高则分配更多的原则，最少分配方案为 [1, 2, 1]，该段总和为 4。 - 对于子段 [8]，只有一个任务，最少分配 1k Token，该段总和为 1。 - 优先级为 0 的任务不分配 Token。 总计最小分配数量为 4 + 1 = 5。
输入
3,5,2,0,8
输出
5

算法解析依据充分

考点：贪心

数据规模 N ≤ 200000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 200000
  • 元素值域：P_i ≤ 1e9（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

本题切入点

等价于分糖果问题：从左到右和从右到左各扫一遍取较大值，保证相邻严格高的分到更多；被 0 和负数切分的子段独立处理。

每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。

思路框架（贪心 通法 · 非本题专属）

  1. 找出「局部最优怎么选」（往往与排序后的顺序有关）。
  2. 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
  3. 按策略一次扫描（通常要先排序）得到答案。
  4. 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。

实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。

复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

  • 策略不成立却当成贪心做（典型错因）。
  • 排序关键字选错，或相同关键字时的次级规则没考虑。

对照本题

  • 数据规模 N ≤ 200000，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3,5,2,0,8 → 输出 5

在该样例中，优先级为 0 的任务将序列分割为两个有效子段：[3, 5, 2] 和 [8]。

  • 对于子段 [3, 5, 2]，为了满足相邻优先级更高则分配更多的原则，最少分配方案为 [1, 2, 1]，该段总和为 4。
  • 对于子段 [8]，只有一个任务，最少分配 1k Token，该段总和为 1。
  • 优先级为 0 的任务不分配 Token。

总计最小分配数量为 4 + 1 = 5。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2026年-华为-04月15号AI岗；2026年-华为-04月15号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解