901. How Far You Get With Bricks and Ladders

A row of n buildings has given heights. You start on building 0 and move only to the next building on the right. Moving from building i to i + 1:

if h[i+1] <= h[i] free otherwise costs (h[i+1] - h[i]) bricks, OR one ladder

You have b bricks and l ladders. A ladder covers any single climb whatever its size. Print the index of the furthest building you can reach, using 0-based indices.

n = 6, b = 10, l = 2, heights 4 2 7 6 9 14 -> 5 n = 4, b = 0, l = 0, heights 1 2 3 4 -> 0 n = 4, b = 0, l = 0, heights 5 4 3 2 -> 3 n = 5, b = 0, l = 4, heights 1 5 9 13 17 -> 4

In the first row the climbs are +5 (from 2 to 7), +3 (from 6 to 9) and +5 (from 9 to 14), with one free descent in between. Two ladders go on the two climbs of 5, and the climb of 3 costs 3 bricks out of 10, so the last building is reached.

The third row has no upward move at all, so nothing is ever spent.

## What most people try first

Using ladders on the first climbs that appear. Wrong whenever there are fewer ladders than climbs: with two ladders and climbs +1, +1, +100 in that order, both ladders are spent on the ones and the 100 has to be paid in bricks, when spending one ladder on the 100 costs a single brick instead.

Using ladders on the largest climbs overall. Right idea, wrong scope, and it is subtle. The largest climbs of the WHOLE row are not the right target, because you may never get that far. The decision has to be made against the climbs seen SO FAR, at every step, which is a different set each time.

Trying every assignment of ladders. There are C(n, l) of them.

## The bounded heap, with the eviction doing the work

Walk left to right. Put every climb on a ladder optimistically. When more than l climbs are on ladders, the smallest of them must come off and be paid in bricks instead.

h = empty MIN-heap of climbs currently on ladders for i from 0 to n-2: c = h[i+1] - h[i] if c <= 0: continue push c if size(h) > l: b = b - pop(h) if b < 0: print i and stop print n-1

This is exactly the bounded heap of problem 880 doing a different job: instead of REPORTING the k largest, it keeps the l largest climbs on ladders and hands everything it evicts to the brick budget. The heap is a MIN-heap because the entry to evict is the smallest of the survivors, which is the same direction argument as before.

## Why the greedy is optimal

At any point, suppose you have reached building i + 1 and the climbs so far are a fixed multiset. Ladders are interchangeable and unlimited in size, so the only question is which l climbs they cover. Covering the l largest minimises the brick total, because swapping a covered climb for a larger uncovered one reduces the bricks paid by the difference, which is non-negative. So the minimum brick spend to reach building i + 1 is the sum of all climbs so far minus the l largest of them, which is exactly what the loop maintains.

Since that minimum is non-decreasing in i, the first i at which it exceeds b is the furthest building reachable.

## Why the answer is i and not i + 1

The loop index i is the building you are standing on when the move to i + 1 turns out to be unaffordable. You already got to i, so i is the answer. Printing i + 1 claims a building you could not pay for, and printing i - 1 throws away one you reached.

## The boundary that breaks a careless implementation

`l = 0`. Every climb is pushed and immediately popped, so every climb is paid in bricks. The code needs no special case, but a version that only consults the heap when l > 0 does.

A flat or descending move. c <= 0 costs nothing and must not enter the heap at all. Pushing a zero wastes a ladder on nothing, and 5 4 3 2 with no resources would then fail at the first step instead of reaching the end.

`n = 1`. There are no moves, and the answer is 0.

## Overflow, with the actual magnitude

The brick budget reaches 10^12, which is already past the signed 32-bit ceiling of 2147483647 before a single climb is subtracted. Reading b into a 32-bit type truncates 1000000000000 to a NEGATIVE number, so the very first eviction reports failure. The test with b = 10^12 and a climb of 999999 answers 2, and a 32-bit build answers 0.

Individual climbs are at most 10^6 and fit anywhere. It is the budget that does not.

## Related problems

Problem 880 uses the same bounded heap to report the k largest values. Problem 883 uses it to keep a running total of the k smallest. Here the evicted values are the ones that matter, which is the third thing to do with one structure.

## Cost

Time O(n log l). Space O(l).

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ b ≤ 1000000000000` - `0 ≤ l ≤ 200000` - `1 ≤ h[i] ≤ 1000000`