P2602.第3题-新能源汽车充电桩建设策略
题目内容
随着新能源汽车的蓬勃发展，新能源汽车充电桩的覆盖密度越来越重要。某汽车公司建设充电桩的思路如下:
一条高速沿线，每个区域建设一个充电站，充电站内有多个充电桩，充电站之间保持合理的距离，每个充电站可以覆盖相邻范围的多个区域
我们使用n来表示区域充电站的数目，使用station[i]数组表示第i个充电站中充电桩的数目。
给定一个范围r，i区域可以被附近范围内的充电站覆盖，∣i−j∣<=r,0<=i,j<=n−1,∣i−j∣表示绝对值。
因此覆盖区域的充电桩包括i区域内充电站的充电桩以及满足上述覆盖条件区域j区域充电站的充电桩。
汽车公司打算在一些城市新增k个充电桩，如何分配这k个充电桩给充电站，使得所有区域总，被充电桩覆盖最少区域的充电桩数目最大化。
输入描述
第一行输入为n，表示有n个充电站区域，取值范围[0,100000]
第二行输入为station[n]数组，表示n个充电站中充电桩的数目[0,100000]
第三行输入为r，表示充电站可覆盖的相邻区域的范围[0,n−1]
第四行输入为k，表示需要新增的充电桩数目[0,1000000000]
输出描述
输出被充电桩覆盖最少的区域的充电桩的数目
样例1
输入
5
1 2 4 5 0
1
2
输出
5
说明
最优方案是把2个充电桩都放在充电站1，这样每个充电站的充电桩数目分别为1 4 4 5 0。
- 区域0的覆盖充电桩为1+4=5,
- 区域1为1+4+4=9，
- 区域2为4+4+5=13，
- 区域3为5+4=9，
- 区域4为5+0=5
充电桩覆盖数目最少是5
无法得到更优解，所以我们返回5。
样例2
输入
4
4 4 4 4
0
2
输出
4
说明
无论怎么分配新增的3个充电站，总有一个区域的充电桩覆盖数目是4
