806. Where to Put the New Stops

A tram line has n stops at strictly increasing positions p[0] < p[1] < ... < p[n-1]. Exactly k new stops are to be added. A new stop may go anywhere on the line, at any real position, including between two existing stops or on top of a spot already chosen.

Print the smallest possible largest distance between two neighbouring stops afterwards, to exactly 6 digits after the decimal point.

stops 0 10, k = 1 -> 5.000000 stops 0 10, k = 3 -> 2.500000 stops 1 2 3 4 5 6 7 8 9 10, k = 9 -> 0.500000 stops 0 1 4 5 100, k = 0 -> 95.000000

## Why this is not problem 259

Problem 259 places items to MAXIMISE the smallest gap, with the positions to choose from given in advance. Here the objective is flipped, the positions are continuous rather than chosen from a list, and the existing stops cannot be moved. The two share the word "gap" and nothing else: here adding a stop always helps, there adding one always hurts.

## What a candidate answer buys you

Fix a largest allowed distance D. A gap of width g has to be cut into pieces of at most D each, so it needs ceil(g / D) pieces and therefore ceil(g / D) - 1 new stops inside it. Add that across the gaps and compare with k:

needed(D) = sum over gaps of (ceil(g / D) - 1)

Since D comes out of a real binary search, g / D is essentially never a whole number, so ceil(g / D) - 1 and floor(g / D) agree and the simpler floor is what the code writes. It is worth knowing WHY the shortcut is safe rather than copying it: with an integer D the two differ whenever D divides g, and the shortcut would be wrong.

## Why the predicate is monotone

A larger D never needs more stops: g / D2 <= g / D for D2 > D, and the ceiling keeps the order. So needed is non-increasing in D, and the workable values of D form a suffix. The answer is where that suffix starts.

## The bounds

lo = 0, which never works for k finite, and hi = the widest existing gap, which always works because no new stop is needed at all.

Note which end is returned. The invariant is "hi works, lo does not", so the answer is hi. Printing lo gives a value just below the true one, which at six decimals often prints the same and occasionally does not, making it one of the nastiest bugs in this topic.

## The boundary that breaks a careless implementation

k = 0. Nothing is added and the answer is the widest gap exactly, which is also hi. A loop that assumes at least one stop is placed, or that starts hi at the average gap, gets it wrong.

The second is spending the budget unevenly. With gaps 2 2 2 and k = 6 the answer is 0.666667, not 1, because all six new stops can be spread two per gap. A greedy that repeatedly splits the current widest gap in half happens to reach the same answer here and does not in general; the counting check is what is actually correct.

## Width

Positions reach 10^9, which a signed 32-bit integer holds. The count of new stops does not: near the answer a single gap can demand 2 * 10^15 of them before the loop notices it has passed k, so a 32 bit accumulator overflows there. Keep that total in a 64 bit integer and break out of the loop the moment it exceeds k.

## Related problems

Problem 797 minimises a jump strength with a plank budget, which is the same shape with whole numbers and a count of failures rather than a count of insertions. Problem 804 divides quantities into equal real parts while maximising instead of minimising.

## Cost

Time O(100 * n). Space O(n).

Constraints - `2 ≤ n ≤ 100000` - `0 ≤ k ≤ 10^6` - `0 ≤ p[i] ≤ 10^9` - the positions are strictly increasing - every answer is at least `10^-9` away from a halfway rounding point at 6 digits