Search for a command to run...
Binary search over real numbers, not integers
Initialization
Any spacing between 0 and the widest existing gap (1.000000) is conceivable. Fewer stations are needed as the allowed distance grows, so the requirement is monotonic.
Binary Search on Real Numbers
1function numberOfGasStationsRequired(dist, arr) {2 const n = arr.length;3 let cnt = 0;4 5 for (let i = 1; i < n; i++) {6 const numberInBetween = Math.floor((arr[i] - arr[i - 1]) / dist);7 8 // Exact fit needs one fewer — the last would land on a station9 if ((arr[i] - arr[i - 1]) === dist * numberInBetween) {10 cnt += numberInBetween - 1;11 } else {12 cnt += numberInBetween;13 }//k: 4low: 0.000000high: 1.00000014 }15 return cnt;16}17 18function minimiseMaxDistance(arr, k) {19 const n = arr.length;20 let low = 0, high = 0;21 22 for (let i = 0; i < n - 1; i++) {23 high = Math.max(high, arr[i + 1] - arr[i]);24 }25 26 const diff = 1e-6;27 while (high - low > diff) {28 const mid = (low + high) / 2.0;29 const cnt = numberOfGasStationsRequired(mid, arr);30 31 if (cnt > k) {32 low = mid; // too tight33 } else {34 high = mid; // achievable35 }36 }37 return high;38}