761. The Smallest Tank That Survives the Drive
A road runs from kilometre 0 to kilometre D. There are n fuel stations, at strictly
increasing positions p[0] < p[1] < ... < p[n-1], all strictly between 0 and D.
A van leaves kilometre 0 with a full tank. The tank holds C litres and the van burns exactly
one litre per kilometre. Stopping at a station fills the tank back to C and costs time, so at
most k stops are allowed on the whole trip. Arriving at a station or at D with the tank
exactly empty is fine; running dry between them is not.
Print the smallest whole C that gets the van to D within k stops.
stations 2 5 8, D = 10, k = 1 -> 5
stations 2 5 8, D = 10, k = 3 -> 3
stations 2 5 8, D = 10, k = 0 -> 10
stations 10 20 30 40, D = 60, k = 2 -> 20
With C = 5 the van drives to kilometre 5, fills up, and reaches 10 on that one tank. With
C = 4 it can only reach station 2, then station 5, then station 8, which is three stops.
## Testing one capacity
Given C, the fewest stops is produced by a greedy rule: always drive to the FARTHEST station
within reach, and refuel there.
That rule is optimal by an exchange argument. Suppose some plan makes its first stop at station
x and the farthest reachable station is y >= x. Replacing x by y leaves the van at least
as far along with a full tank, so every later stop in the plan is still reachable. Repeating the
swap turns any plan into the greedy one without ever adding a stop, so the greedy plan uses the
fewest.
Walking the stations with a pointer that only ever moves forward makes the whole check O(n),
not O(n) per hop.
## Why the predicate is monotone
Enlarging the tank never removes an option: every hop that was within C is within C + 1. So
any plan valid for C is valid for every larger capacity, and the fewest stops needed is
non-increasing in C. Capacities that finish within k stops therefore form a suffix, and
binary search finds the first one.
## The bounds
lo = 1. hi = D, which needs no stops at all and is therefore always a valid answer, so the
search can never fail. That is worth noticing: this problem has no -1 case even though it looks
like it should.
## The boundary that breaks a careless implementation
Reaching exactly. A station at distance exactly C IS reachable, and the arrival at D counts
when pos + C >= D, not >. Writing either comparison strictly makes stations 2 5 8 with
k = 1 report 6 rather than 5, and the error shows up only on inputs where the answer divides
the road evenly.
The other boundary is the forward pointer: it must not be reset at the start of each hop. Stations already passed can never be useful again, and rescanning them from zero turns the check quadratic on the inputs with the most stations.
## Overflow
This is a good place to bound an expression instead of eyeballing it, because eyeballing gets it
wrong. pos is either 0 or a station position, and every station sits strictly below D, so
pos <= D - 1 <= 999999999. C never rises above hi = D <= 10^9. The largest pos + C can
be is therefore 1999999999, and a 32-bit signed integer holds up to 2147483647. It fits, with
about seven percent of the range to spare.
The margin is thin and it is the bound hi = D that provides it. Search a wider range, or allow
a station at D rather than strictly below it, and the sum crosses the line. Write pos + C in
64 bits in C, C++ and Java for that reason, not because the arithmetic as specified overflows.
## Related problems
Problem 1645 finds the route whose worst edge is smallest, which is the same idea of testing a candidate limit by asking whether the journey is possible under it. Here the test is a greedy walk rather than a reachability search, and the answer is a capacity rather than an edge weight.
## Cost
Time O(n log D). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `2 ≤ D ≤ 10^9` - `0 ≤ k ≤ n` - `0 < p[0] < p[1] < ... < p[n-1] < D`
Input
The first line contains three integers n, D and k.
The second line contains n integers p[0] ... p[n-1], the station positions in strictly increasing order.
Output
Print one integer, the smallest tank capacity in litres that completes the drive within k stops. 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.