华为 · 堆 · 算法编程题
华为 堆 n ≤ 1e3 时限 1 秒 / 256 MB

题目描述

小红正在术式终端上维护一套由 n 个魔导模块构成的核心系统。每个模块 i 在运行时的执行耗时为 a_i 。根据术士协会的规程，每个模块都有一个性能下限 b_i ，即该模块的执行耗时无论如何优化都不能低于 b_i 。
小红计划在接下来的 m 天内，每天对其中一个模块进行一次效能迭代。如果选中的模块当前耗时为 t ，经过一次迭代后，其新耗时将变为 max(⌈ t / 2 ⌉, b_i) 。其中 ⌈ x ⌉ 表示对 x 向上取整。
请问在 m 天的优化结束后，所有模块的执行耗时之和最小是多少？

输入输出

输入描述
第一行包含两个整数 n 和 m ( 1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000 )，分别表示模块的数量和优化的总天数。
第二行包含 n 个整数 a_1, a_2, ..., a_n ( 1 ≤ a_i ≤ 10^5 )，表示各模块的初始执行耗时。
第三行包含 n 个整数 b_1, b_2, ..., b_n ( 1 ≤ b_i ≤ a_i ≤ 10^5 )，表示各模块允许的执行耗时下限。
输出描述
输出一个整数，表示 m 天后所有模块执行耗时之和的最小值。

样例共 1 组

样例 1 · 在样例中， n=2, m=3 ： - 第 1 天：优化模块 1，其耗时从 100 变为 max(⌈ 100/2 ⌉, 40) = 50 。 - 第 2 天：优化模块 2，其耗时从 80 变为 max(⌈ 80/2 ⌉, 10) = 40 。 - 第 3 天：再次优化模块 2，其耗时从 40 变为 max(⌈ 40/2 ⌉, 10) = 20 。 最终各模块的耗时分别为 50 和 20 ，总和为 50 + 20 = 70 。此时总和达到最小。
输入
2 3
100 80
40 10
输出
70

算法解析依据充分

考点：堆

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

题目画像

  • 数据规模：n ≤ 1e3，m ≤ 1e3
  • 元素值域：a_i ≤ 1e5，b_i ≤ 1e5（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：堆

本题切入点

每次迭代的最优选择是「当前能减少最多的模块」：用最大堆按 (t − max(⌈t/2⌉, b)) 的收益维护，逐天弹出更新后压回，m 天后求总和。

用堆在 O(log n) 内取极值，求 TopK 与动态中位数。

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

  1. 求最大 K 个：维护大小 K 的小根堆，超了就把堆顶弹出。
  2. 动态中位数：用「对顶堆」——小的一半放在大根堆，大的一半放在小根堆，两个堆顶就是中位数。
  3. 移动窗口中的中位数需要配合「延迟删除」处理过期元素。

实现要点：Python 的 heapq 是小根堆，要大根堆就存负数。

复杂度：时间 O(n log k) / O(n log n) ｜ 空间 O(k)

该范式的通法易错点

  • 求第 K 大时堆类型选反（小根堆还是大根堆）。
  • 窗口滑出元素时忘记从堆里清理或标记过期。

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 2 3 / 100 80 / 40 10 → 输出 70

在样例中， n=2, m=3 ：

  • 第 1 天：优化模块 1，其耗时从 100 变为 max(⌈ 100/2 ⌉, 40) = 50 。
  • 第 2 天：优化模块 2，其耗时从 80 变为 max(⌈ 80/2 ⌉, 10) = 40 。
  • 第 3 天：再次优化模块 2，其耗时从 40 变为 max(⌈ 40/2 ⌉, 10) = 20 。

最终各模块的耗时分别为 50 和 20 ，总和为 50 + 20 = 70 。此时总和达到最小。

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

本题来源：2026年-华为-04月08号研发岗。

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