No testdata at current.
二分每个区域被覆盖的最小充电桩数量,每个区域至少需要这么多的充电桩数量,对于给定的最低充电桩数量,判断是否可以在只分配k个充电桩的情况下实现。
贪心的做法是从左到右遍历,计算当前区域的充电桩数量,如果低于最低充电桩数量,则尽量放置充电桩在最右侧的区域,因为这样可以让右边更多的区域增加充电桩。
由于计算当前区域的充电桩数量需要累计附近的充电桩,所以每个区域的充电桩其实可以视为对一个区间的区域进行累加,在遍历过程中维护当前的充电桩数量比较简单,所以建议采用差分的方式来计算累计充电桩。
本题属于以下题库,请选择所需题库进行购买