充电桩最优布局规划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分别表示区域总数、计划建设的充电站数量、充电站间的最小距离要求整数数组表示各区域的充电需求量区域数量 n1≤n≤2000充电站数量 m1≤m≤200最小距离 k1≤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满足最小距离要求最大总需求205070示例2输入5,2,2,[5,10,5,10,5]输出20说明区域数量5计划建设 2 个充电站最小间距 2 各区域需求 [5,10,5,10,5]最优选择选择区域 2(10) 和区域 4(10)它们之间距离为 2满足最小距离要求最大总需求101020示例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 更新确保窗口外的状态被正确维