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

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

题目描述

网络规划团队正在为某一线型工业园区的网络建设制定方案。园区由一条笔直的道路贯穿，沿途分布着 n 个关键业务区域，其位置坐标由整数数组 positions 表示（数组成员严格递增）。

为了保证无缝漫游体验，方案要求相邻两个基站之间必须有足够的重叠覆盖区域，重叠区域长度至少为 minOverlap 米（即：相邻两个基站覆盖区间的交集长度至少为 minOverlap）。

团队手中有 m 个新型基站可用，为践行绿色节能理念，团队希望将基站的发射功率调整到最低（即覆盖半径最小）。

现给定关键区域的位置数组 positions（-10^9≤positions[i]≤10^9）、必须满足的最小重叠区域 minOverlap（0≤minOverlap≤10^9）以及可用的基站数量 m（1≤m≤10^5）。

请计算在满足所有关键区域被覆盖、且相邻基站重叠满足要求的条件下，基站所需的最小信号覆盖半径 k。k 是非负整数，所有基站使用相同半径。

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

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

输入描述

输入共三行：

第一行是严格递增的关键区域坐标，坐标之间使用英文逗号分隔。

第二行是最小重叠长度 minOverlap。

第三行是最多可以使用的基站数量 m。

输出描述

输出一个整数，表示满足条件的最小覆盖半径 k。

示例1

输入

0,10,20
0
2

输出

5

说明

关键区域点间距为 10，需要 2 个基站覆盖 3 个关键区域点。两个半径为 5 的基站可分别覆盖 [0,10] 和 [10,20]，两者在位置 10 处相接，满足重叠长度为 0 的要求。

示例2

输入

0,6,12
2
2

输出

4

说明

两个半径为 4 的基站可以覆盖 [0,8] 和 [4,12]，重叠区间长度为 4，不小于 2。半径为 3 时无法同时完成覆盖和重叠要求，因此答案为 4。

示例3

输入

10
1
1

输出

说明

只有一个关键区域时，把基站中心放在该位置即可，半径为 0。单个基站不存在相邻基站，因此不需要检查重叠。

解题思路

核心思想

设关键区域最左坐标为 L，最右坐标为 R，需要覆盖的总跨度为 D=R-L。

每个半径为 k 的基站覆盖长度为 2k。第一座基站从 L 开始覆盖时，最右端可以到达 L+2k。为了让相邻基站的重叠长度至少为 minOverlap，后续每增加一座基站，覆盖右端最多向右推进：

2k-minOverlap

如果使用 q 座基站，能够连续覆盖的最大长度为：

2k+(q-1)×(2k-minOverlap)

题目给出的是最多可使用 m 座基站。若一座基站已经能够覆盖整个跨度，则不需要考虑重叠；否则，当 2k-minOverlap 大于 0 时，使用更多基站不会降低覆盖能力，因此直接检查 m 座基站的最大覆盖长度即可。

半径越大，覆盖方案越容易成立，可行性具有单调性，因此可以二分查找最小可行半径。

算法步骤

1. 如果只有一个关键区域，直接返回 0。
2. 计算最左和最右关键区域之间的跨度 D。
3. 设置二分下界为 0，上界为 ceil(D/2)，因为一座基站一定可以用该半径覆盖全部关键区域。
4. 对候选半径 k，先计算单个基站的覆盖长度 2k。
5. 如果 2k≥D，则一座基站即可完成覆盖，当前半径可行。
6. 否则，如果只有一座基站，或者 2k≤minOverlap 导致后续基站无法向右推进，则当前半径不可行。
7. 计算 m 座基站能够连续覆盖的最大长度，判断是否达到 D。
8. 根据可行性收缩二分区间，最终得到最小半径。

复杂度分析

设坐标跨度为 D。每次可行性判断只进行常数次运算，二分次数为 O(log D)，因此时间复杂度为 O(log D)，额外空间复杂度为 O