760. The Cap That Lands Nearest the Target
n departments have asked for a[i] units of equipment each. You must announce one whole
number v, after which every department receives min(a[i], v): departments that asked for
v or fewer get exactly what they asked for, and the rest get v.
Choose v so the total handed out is as close as possible to target. If two values of v are
equally close, print the smaller one.
requests 4 9 3, target 10 -> 3
requests 2 3 5, target 10 -> 5
requests 2 2 2 2, target 7 -> 2
requests 4 4, target 5 -> 2
With requests 4 9 3 and v = 3 the total is 3 + 3 + 3 = 9, one away from 10. With v = 4
it is 4 + 4 + 3 = 11, also one away, so the smaller v wins.
## What most people try first
Binary searching on the DISTANCE to the target. It is the thing the question asks about, so it is the natural thing to search, and it does not work: the distance falls and then rises again, so it is not monotone and there is no single crossing point for a search to find.
The fix is to search a different statement entirely, one that IS monotone, and recover the answer from where it turns over.
## The objective is NOT monotone
Write
f(v) = min(a[0], v) + min(a[1], v) + ... + min(a[n-1], v)
f is non-decreasing in v, because each term is. But what the problem asks to minimise is
abs(f(v) - target), and that is not monotone at all: it falls while f climbs towards the
target and rises afterwards, a V shape. Binary searching on "is this v better than that one"
is meaningless, and this is the trap the problem exists for.
Binary search the MONOTONE thing instead, and recover the answer from it.
## What to search on
f(v) >= target IS monotone: since f only grows, once it reaches the target it stays there.
So find the smallest v with f(v) >= target. Call it v0.
The best answer is then either v0 or v0 - 1, and nothing else, because f is below the
target everywhere left of v0 and at or above it everywhere right, so moving further away in
either direction can only increase the distance. Compare
f(v0) - target against target - f(v0 - 1)
and take v0 - 1 on a tie, which is exactly the rule the statement asks for.
## The bounds and the two special cases
lo = 0, because v = 0 is allowed and gives a total of zero, which is the right answer when
the target is 0.
hi = max(a), because beyond it every department already gets what it asked for and f stops
changing. That is also the case to handle separately: if f(max(a)) <= target then f never
reaches the target, the distance is still falling at the top of the range, and the answer is
max(a).
## The boundary that breaks a careless implementation
v0 = 0. Then v0 - 1 does not exist and evaluating f(-1) is meaningless; the answer is
simply 0. This happens exactly when the target is 0.
## Overflow
f(v) reaches 10^5 * 10^9 = 10^14. The differences are small, but the totals they come from
are not, so the accumulator is 64-bit.
## Related problems
Problem 759 searches for the last feasible value instead of the first. This one goes one step further: the quantity being optimised is not monotone, so the search runs on a different predicate and the answer is recovered from the seam afterwards.
## Cost
Time O(n log(max a)). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ target ≤ 10^9` - `1 ≤ a[i] ≤ 10^9`
Input
The first line contains two integers n and target.
The second line contains n integers a[0] ... a[n-1], the requested amounts.
Output
Print one integer, the value v whose total is closest to the target, taking the smaller v when two are equally close. Print it alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.