Baseline Binary Search · In Search Space O(N log M), where M is the initial maximum gap · O(1)
A highway authority places k additional toll gantries between existing ones, at any positions along the corridor, to shrink the longest stretch a driver travels without passing a gantry. Choose the k placements to minimize that longest stretch. Report the optimized distance to two decimal places.
Input: An integer N, an array stations of N sorted positions, and an integer K, the number of new stations to add.
Output: The smallest achievable maximum distance between adjacent stations, rounded to two decimal places.
1 <= N <= 10^50 <= K <= 10^50 <= stations[i] <= 10^9positions are given in strictly increasing orderInput: {"N":10,"stations":[1,2,3,4,5,6,7,8,9,10],"K":9}
Output: 0.5
Nine new stations slot one between each existing pair, halving every unit gap to 0.50.
Input: {"N":10,"stations":[3,6,12,19,33,44,67,72,89,95],"K":2}
Output: 14
The widest initial stretches are 23 and 24; two well-placed stations pull the worst stretch down to 14.