355. Extra Charging Posts
Electric cars drive along a straight road, and stations[i] is the position in kilometres of the i-th charging post, given in non-decreasing order. A company will build exactly k new posts, and a new post may be placed anywhere on the road, not only at whole kilometres.
After the new posts are built, look at every pair of neighbouring posts, old or new, and consider the largest distance between such neighbours. Return the smallest value that this largest distance can be made. An answer within 10^-6 of the correct value is accepted. The first and last existing posts are at different positions.
Example 1
- Input:
- stations = [1,2,3,4,5], k = 3
- Output:
- 1
- Explanation:
The four gaps are all 1 km. Three new posts can split three gaps in half, but one gap of 1 km remains, so the largest distance stays 1.
Example 2
- Input:
- stations = [1,5,6], k = 2
- Output:
- 1.3333333333333333
- Explanation:
The gaps are 4 and 1. Putting both new posts in the 4 km gap cuts it into three parts of 4/3 each, so the largest distance is 4/3, about 1.3333.
Constraints
2 ≤ stations.length ≤ 105
0 ≤ stations[i] ≤ 108, and stations[0] < stations[n - 1]
0 ≤ k ≤ 106
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
- Tolerance
0.000001- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log(M / eps)), with a fixed number of iterations
- Space
- O(1)