766. Setting the Sawmill Blade
A sawmill has one horizontal blade that runs the length of the yard. The blade is set to a
whole-number height h and shears the top off every tree at once: a tree of height a[i]
contributes a[i] - h metres of timber if it is taller than h, and nothing at all if it is
not. Trees shorter than the blade are left standing.
You need at least m metres of timber and you would like to take as little as possible, so
print the HIGHEST whole-number blade setting that still yields at least m metres. The blade
may be set to 0.
a = 20 15 10 17, m = 7 answer 15 5 + 0 + 0 + 2 = 7
a = 4 42 40 26 46, m = 20 answer 36 0 + 6 + 4 + 0 + 10 = 20
a = 5 5 5, m = 0 answer 5 nothing is needed, so cut nothing
a = 10 10 10 10, m = 40 answer 0 every metre of every tree is required
## The shape of the answer
The obvious method is to try every height from max(a) downwards until the yield is enough.
With heights up to 10^9 that is 10^9 sweeps of 2 * 10^5 trees.
The yield function is the thing to look at:
yield(h) = sum over i of max(0, a[i] - h)
It is not linear, because trees drop out of the sum one by one as the blade rises. But it is non-increasing, and that is all binary search needs.
## Why the count is exactly right, not an estimate
Several problems in this block need an argument that a greedy choice is optimal. This one does
not, and it is worth being explicit about why: there is no choice. For a fixed h the yield is
determined, because every tree is cut by the same blade in the same pass. The predicate is a
direct evaluation of the rule, so "is h good enough" is answered by arithmetic rather than by
strategy.
Recognising which problems are like this and which need a proof is most of the skill. Compare #251, where the day count really is a greedy decision that has to be justified.
## Why the predicate is monotone
Raise the blade by one metre. Each tree strictly taller than h loses exactly one metre, each
tree at or below h was already contributing nothing and still contributes nothing. So the
yield never rises when h rises. The heights that produce at least m therefore form a prefix
0 .. answer, and the answer is the last one.
## The bounds
lo = 0, because the blade may sit on the ground and that is the most productive setting
possible. hi = max(a), because at that height nothing is cut at all, giving yield 0. Both ends
are attainable settings, which matters: a bound that is not itself a legal answer makes the
final lo == hi value meaningless.
The input guarantees m <= sum(a), so the answer always exists. Without that guarantee you
would also have to report failure, as problem 765 does.
## The boundary that breaks a careless implementation
Two separate off-by-ones live here.
First, m = 0. Every height is feasible, including max(a), so the answer is max(a) and not
max(a) - 1. Code that starts hi = max(a) - 1 because "cutting at the tallest tree is
pointless" is wrong on this input alone.
Second, the yield must use max(0, a[i] - h) and not a[i] - h. Letting a short tree
contribute NEGATIVE timber makes it eat into what the tall trees produced, which understates the
yield and drives the blade down. On 8 0 0 0 0 with m = 4 the unguarded version computes
8 - 5h and reports a blade height of 0, where the correct answer is 4.
## Overflow
2 * 10^5 trees of height 10^9 give 2 * 10^14 metres at h = 0, and m itself may be that
large. A 32-bit accumulator wraps, the comparison against m goes the wrong way, and the search
converges on a confident wrong height.
## Cost
Time O(n log(max a)). Space O(1) beyond the input. Sorting the trees would let each check be
a binary search plus a suffix sum, O(log n) per probe, but the plain sweep is already fast
enough and is much harder to get wrong.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a[i] ≤ 10^9` - `0 ≤ m ≤ sum of all heights`
Input
The first line contains two integers n and m.
The second line contains n tree heights.
Output
Print one integer on its own line: the highest whole-number blade setting whose yield is at
least m metres. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.