797. The Jump You Have to Train For
A stream is crossed by n stepping stones at strictly increasing positions
p[0] < p[1] < ... < p[n-1]. You start on the first stone and must finish on the last, landing on
EVERY stone on the way; stones may not be skipped.
Crossing the gap from p[i] to p[i+1] unaided needs a jump strength of at least
p[i+1] - p[i]. You also carry k planks. Laying a plank over one gap crosses it whatever its
width, and each plank can be used for one gap only.
Print the smallest jump strength that gets you across.
stones 0 2 5 9 10, k = 1 -> 3
stones 0 2 5 9 10, k = 0 -> 4
stones 0 2 5 9 10, k = 4 -> 0
The gaps are 2, 3, 4 and 1. With one plank the widest gap is bridged and the strength has to cover the remaining 2, 3 and 1, which is 3. With no plank it has to cover 4.
## Why trying every strength is too slow
A candidate strength J is easy to test: count the gaps wider than J and ask whether that count
fits in k planks. That is one pass, O(n).
Trying J = 0, then 1, then 2 costs one pass each. Positions reach 2 * 10^9, so a gap can be
that wide and the scan is 2 * 10^9 passes.
## Why the predicate is monotone
Raising J can only remove gaps from the "too wide" list; it never adds one, because
g > J + 1 implies g > J. So the number of planks needed is non-increasing in J, and once a
strength is enough every larger strength is too. The answers read no no no YES YES, and the
answer is the first YES.
## The bounds
lo = 0, which is right when k is at least the number of gaps.
hi = max gap. At that strength no gap needs a plank at all.
## The other accepted solution, and why it is worth knowing
Sort the gaps in decreasing order and print the gap at index k, or 0 when there are k gaps or
fewer. The planks go on the k widest gaps and the strength must cover the next one down.
That is O(n log n) and it is genuinely simpler here. The binary search is worth writing anyway
because it survives a change the sort does not: if planks came in two grades, or cost money, or
could only be laid on gaps within a certain span, the "take the k widest" argument collapses
while the counting check just gains a line. Which one to reach for is the judgement this problem
is really about.
## The boundary that breaks a careless implementation
A single stone. There are no gaps, no jump is ever made, and the answer is 0. A program that
takes the maximum of an empty list crashes, and one that starts hi at 1 prints 1.
The second is k at least n - 1, where every gap is planked and the answer is 0 however wide
the stream is.
## Related problems
Problem 765 cuts ribbons to one WHOLE length, and problem 803 asks the same question with a real length so that the counting argument has to survive division without rounding.
## Cost
Time O(n log(max gap)). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ k ≤ n` - `0 ≤ p[i] ≤ 2 * 10^9` - the positions are strictly increasing
Input
The first line contains two integers n and k, the number of stones and the number of planks.
The second line contains n integers p[0] ... p[n-1], the stone positions in increasing order.
Output
Print one integer, the smallest jump strength that crosses the stream given k planks. Print it alone on one line, with no units.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.