759. How Long the Laptops Can All Stay On

A lab has n laptops and m batteries; battery j holds b[j] minutes of charge. All n laptops must be running at every moment. A battery powers one laptop at a time, may be moved between laptops as often as you like at no cost, and is used up once its charge is gone. Batteries cannot be recharged.

Print the greatest whole number of minutes for which all n laptops can run together.

laptops 2, batteries 3 3 3 -> 4 laptops 2, batteries 1 1 1 1 -> 2 laptops 3, batteries 5 5 5 -> 5 laptops 3, batteries 7 7 7 1 -> 7

With two laptops and three batteries of 3 minutes the answer is 4, and reaching it takes all three batteries, because no battery on its own can power a laptop for longer than 3 minutes. One schedule that works: laptop A runs on battery 1 for minutes 0 to 3 and on battery 2 for minutes 3 to 4; laptop B runs on battery 2 for minutes 0 to 2 and on battery 3 for minutes 2 to 4. Battery 2 is shared, but the two stretches do not overlap, so it is never powering both laptops at the same instant. Two laptops for 4 minutes need 2 * 4 = 8 laptop-minutes, the batteries hold 9, and the leftover unit is the one minute of battery 3 nobody uses.

Five minutes fails on the total charge alone: it would demand 2 * 5 = 10 laptop-minutes against 9 units available, and no arrangement can conjure the missing one. The other half of the condition, that a battery gives at most T minutes because it powers one laptop at a time, is not what bites in this example. To see that half bite, take 10 1 1 with two laptops. The charge totals 12, which on paper would cover 6 minutes, but the 10-minute battery can contribute only T of it, so at T = 6 the supply is 6 + 1 + 1 = 8 against a demand of 12 and the answer collapses all the way to 2.

## The condition for a candidate run of T minutes

Total demand is n * T laptop-minutes. Battery j can supply at most min(b[j], T): it cannot give more charge than it holds, and it cannot give more than T minutes because it only ever powers one laptop at a time. So

sum over j of min(b[j], T) >= n * T

is NECESSARY. It is also sufficient. Lay the n laptops out as n slots of length T, take the batteries in any order and pour each one into the current slot, spilling over into the next slot when a slot fills. No battery is ever split across two slots at the same INSTANT, because each piece it contributes has length at most T and the two pieces sit at the end of one slot and the start of the next. So the condition is exactly right.

## Why the predicate is monotone

If all the laptops can run for T minutes, they can certainly run for T - 1: stop early. So the feasible values form a PREFIX 0, 1, ..., answer, and the search is for the LAST true rather than the first. That is the mirror image of every other problem in this block and it changes the loop.

## The bounds

lo = 0, always feasible. hi = sum(b) / n rounded down, because n * T can never exceed the total charge available.

## The boundary that breaks a careless implementation

Searching for the last true with lo = mid on success needs the UPPER mid-point:

mid = lo + (hi - lo + 1) / 2

With the ordinary lower mid-point, lo and hi adjacent and the candidate feasible, mid comes out equal to lo and the assignment lo = mid changes nothing. The loop then spins forever. It is the single most common way this shape of search is written wrong, and it only shows up on inputs whose answer is reached from below.

## Overflow

sum(b) reaches 10^5 * 10^9 = 10^14, and so does n * T. Both need 64 bits. The individual min(b[j], T) is small, which is what makes the overflow easy to miss.

## Related problems

Every other problem in this block searches for the first feasible value. This one searches for the last, and problem 760 goes further still: there the objective is not monotone at all and the search has to be run on something else.

## Cost

Time O(m log(sum(b) / n)). Space O(m).

Constraints - `1 ≤ n ≤ m ≤ 100000` - `1 ≤ b[j] ≤ 10^9`