华为校招机试 - 新能源汽车充电桩建设策略（20240124）

题目描述

随着新能源汽车的蓬勃发展，新能源汽车充电桩的覆盖密度越来越重要。

某汽车公司建设充电桩的思路如下：

将一座城市划分为多个区域，每个区域建设一个充电站，充电站内有多个充电桩，充电站之间保持合理的距离，每个充电站可以覆盖相邻范围的多个区域，我们使用

• n 来表示区域充电站的数目
• station[i] 数组表示第 i 个充电站中充电桩的数目

给定一个 r 范围，i 区域可被邻近 r 范围内的充电站覆盖，

• | i - r | ≤ n
• 0 ≤ i，r ≤ n - 1
• | i - r | 表示绝对值

因此覆盖区域 i 的充电桩的包括： i 区域充电站的充电桩及满足上述覆盖条件 i 区域充电站的充电桩。

汽车公司打算在某个城市新增 k 个充电桩，如何分配这 k 个充电桩给充电站（k个充电桩可以增加在不同的充电站），以使得所有区域中，被充电桩覆盖最少区域的充电桩数目最大化。

输入描述

第一行输入为 n，表示有 n 个充电站区域

• n ∈ [0, 100000)

第二行输入为 station[n] 数组，表示 n 个充电站中充电桩的数目

• station[i] ∈ [0, 100000]

第三行输入为 r，表示充电站可覆盖的相邻区域的范围

• r ∈ [0, n-1]

第四行输入为 k，表示需要新增的充电桩的数目

• k ∈ [0, 100