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

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

题目描述

某城市计划在一条主要街道两侧建设电动汽车充电桩，以满足日益增长的充电需求。街道被划分为 n 个连续的区域，每个区域都有预估的充电需求量。

为了最大化投资效益，规划部门希望选择 m 个区域建设大型充电站（每个充电站占据一个区域），并且要求任意两个充电站之间的距离至少为 k 个区域。

给定街道各区域的充电需求预测数据，请帮助规划部门确定最优的充电站布局方案，使得所选区域的充电需求总和最大。

注意：距离是指两个区域索引之间的差值，例如区域 i 和区域 j 之间的距离为 abs(i−j)。

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

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

输入描述

三个整数 n、m、k，分别表示区域总数、计划建设的充电站数量、充电站间的最小距离要求

整数数组，表示各区域的充电需求量

区域数量 n：1≤n≤2000

充电站数量 m：1≤m≤200

最小距离 k：1≤k≤100

各区域充电需求：0≤ 需求 ≤10000

输出描述

返回一个整数，表示在满足约束条件下能够获得的最大充电需求总和。

注意：测试用例保证输入数据合法，至少存在一种满足条件的选址方案

示例1

输入

5,2,3,[10,20,30,40,50]

输出

70

说明

区域数量：5，计划建设 2 个充电站，最小间距 3

各区域需求：[10,20,30,40,50]

最优选择：选择区域 2(20) 和区域 5(50)，它们之间距离为 3，满足最小距离要求

最大总需求：20+50=70

示例2

输入

5,2,2,[5,10,5,10,5]

输出

20

说明

区域数量：5，计划建设 2 个充电站，最小间距 2 各区域需求 [5,10,5,10,5]

最优选择：选择区域 2(10) 和区域 4(10)，它们之间距离为 2，满足最小距离要求

最大总需求：10+10=20

示例3

输入

1,1,1,[10]

输出

10

说明

区域数量：1，计划建设 1 个充电站，最小间距 1

各区域需求 [10]

最优选择：选择区域 1(10)，只有 1 个，满足最小距离要求

最大总需求：10

解题思路

本题是一个典型的动态规划问题，核心在于维护选中了不同数量充电站时的最大需求。

关键观察：

1. 相邻两个充电站之间的距离至少为 k
2. 选择当前位置时，前一个充电站最远可以在 i-k 位置
3. 使用滑动窗口维护 best[c]，表示前 i-k 个位置中选了 c 个的最大值

状态定义

• dp[i][c]: 选择到第 i 个位置（包含 i），共选了 c 个充电站的最大需求
• best[c]: 前 i-k 个位置中选了 c 个充电站的最大需求

状态转移

dp[i][1] = demands[i]  // 只选当前位置

dp[i][c] = best[c-1] + demands[i]  // 选当前位置 + 前c-1个的最优

best[c] = max(best[c], dp[i-k][c])  // 滑动窗口更新

复杂度分析

• 时间复杂度: O(n * m)
• 空间复杂度: O(n * m)，可优化到 O(m)

正确性证明

定理：算法返回的最大需求等于满足距离约束的 m 个充电站最大需求总和。

证明（数学归纳法）：

1. 基础情况：i < k 时，只有 dp[i][1] 有意义
2. 归纳假设：假设前 i-1 个位置的状态都正确
3. 归纳步骤：
   • dp[i][1] = demands[i]：只选当前位置
   • dp[i][c] = best[c-1] + demands[i]：best[c-1] 包含所有距离约束
   • best 更新确保窗口外的状态被正确维