华为 · 二分 · 算法编程题
华为 二分 n ≤ 1e5 时限 3 秒 / 256 MB

题目描述

在一个古老的王国中，为了抵御来自暗影裂隙的侵蚀，魔法师们沿边境线建立了一排共 n 座哨兵塔。每座哨兵塔都配备有一定数量的“以太信标”，用于维持一个覆盖全境的魔法屏障。
我们用一个下标从 0 开始的整数数组 T 来表示这排哨兵塔，其中 T[i] 代表第 i 座哨兵塔当前已激活的以太信标数量。
每一个位于哨兵塔 i 的信标，都能投射出半径为 的保护辉光，为所有满足距离条件 |i - j| ≤ 的哨兵塔 j 贡献一份屏障能量。一座哨兵塔 j 的“屏障强度” S_j 定义为所有能覆盖到它的以太信标的总数。
现在，皇家魔法议会批准了一项紧急增援计划，允许你额外部署 个新的以太信标。这些信标可以被自由地分配到任意一座或多座哨兵塔中（即，同一座哨兵塔可以增设多个信标）。
你的任务是，作为王国的首席战略家，设计一个最优的信标部署方案，使得所有哨兵塔中**最低的屏障强度**能够被**最大化**。你需要返回这个可以达到的、最大化的最低屏障强度值。

输入输出

输入描述
输入包含四行：
1. 第一行是一个整数 ，代表信标的保护辉光半径。
2. 第二行是一个整数 ，代表可供部署的新信标总数。
3. 第三行是一个整数 n ，代表哨兵塔的总数。
4. 第四行是 n 个用空格分隔的整数，代表数组 T ，即每座哨兵塔初始的信标数量。
数据范围约束：
0 ≤ < n
0 ≤ ≤ 10^9
1 ≤ n ≤ 10^5
0 ≤ T[i] ≤ 10^5
输出描述
返回一个整数，该整数代表在最优部署方案下，整个哨兵塔网络中最低屏障强度的最大可能值。

样例共 1 组

样例 1
输入
19
100
20
10 2 5 8 12 1 1 20 4 3 15 6 9 7 11 18 13 14 17 16
输出
292

算法解析依据充分

考点：二分

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

题目画像

  • 数据规模：n ≤ 1e5
  • 元素值域：T[i] ≤ 1e5（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：二分

本题切入点

「最大化最低屏障强度」是二分答案的标志性问法：二分目标值 v，再用差分/滑动窗口 O(n) 判断能否用 ≤w 个新增信标把每座塔的屏障强度都抬到 v。

把「求最优值」转化为「判定某值是否可行」，用单调性二分逼近答案。

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

  1. 确认单调性：答案越大/越小，条件越容易（或越难）满足。
  2. 写出 check(x)：判断值为 x 时是否可行。
  3. 在答案区间 [lo, hi] 上二分，每次取 mid 调 check，收缩区间。
  4. 边界收敛到唯一答案，注意取整方向（求最小可行值用上取整）。

实现要点：模板：while (lo < hi) { mid = (lo+hi)/2; if (check(mid)) hi = mid; else lo = mid+1; } 求最小可行值。

复杂度：时间 O(check 的代价 × log(答案范围)) ｜ 空间 O(1)

该范式的通法易错点

  • check 函数不满足单调性却硬套二分（会得到错误答案）。
  • 二分边界或取整方向写错，陷入死循环或漏掉边界答案。

对照本题

  • 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：19 / 100 / 20 / 10 2 5 8 12 1 1 20 4 3 15 6 9 7 11 18 13 14 17 16
  • 输出：292

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

本题来源：2025年秋招-华为-9月17号开发岗。

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