751. The Slowest Speed That Still Finishes

A scanning room holds n stacks of paper; stack i has a[i] sheets. The scanner is booked for h whole hours, and within any one hour it touches ONE stack only. At speed k sheets per hour it removes k sheets from the stack it is working on, and if fewer than k sheets remain it takes what is left and idles for the rest of that hour.

Print the smallest whole speed k that clears every stack within h hours.

stacks 3 6 7, h = 8 -> 3 stacks 30 11 23, h = 4 -> 23 stacks 4 4 4, h = 6 -> 2 stacks 4 4 4, h = 5 -> 4

At speed 3 the stacks take 1, 2 and 3 hours, which is 6 of the 8 available. At speed 2 they take 2, 3 and 4, which is 9, so 3 is the first speed that fits.

## Why trying every speed is too slow

The hours a speed needs are easy to count:

hours(k) = ceil(a[0] / k) + ceil(a[1] / k) + ... + ceil(a[n-1] / k)

so the obvious program tries k = 1, then 2, then 3, and stops at the first one that fits. Each attempt costs O(n) and the answer can be as large as 10^9, so at the limits that is 10^14 operations.

## Why the predicate is monotone

Take two speeds with k < k2. For any stack, a / k2 <= a / k, and rounding up preserves a <=, so ceil(a / k2) <= ceil(a / k). Every term of the sum drops or stays, therefore

hours(k2) <= hours(k) whenever k2 > k

hours is non-increasing in k. So if some speed finishes inside h hours, every faster speed does too. The answers to "does k work?" read

no no no no YES YES YES YES

and the whole task is to find the seam. That is the only property binary search needs. Nothing here is sorted, and nothing needs to be.

## The bounds, and why hi is reachable

lo = 1, because a speed of 0 never removes a sheet.

hi = max(a). At that speed every stack is emptied in its first hour, so the total is exactly n hours, and the constraints promise h >= n. The top of the range is therefore guaranteed to work, which is what stops the search from returning a value that does not.

Setting hi to h, or to sum(a) / h, is wrong. The first two examples above already break both: the answer 23 is larger than h = 4.

## The boundary that breaks a careless implementation

Rounding up with integer division is (a + k - 1) / k, never a / k + 1. The second version adds a phantom hour whenever k divides a exactly: with a = 4 and k = 2 the true cost is 2 hours and the wrong formula says 3. The case 4 4 4 with h = 6 is in the tests precisely because the division comes out exact there.

The second trap is the counting loop itself. It must abandon a candidate the moment the running total passes h. Without that, k = 1 on the largest input adds 10^5 terms of 10^9.

## Overflow

The hour total is the thing that overflows. At k = 1 it is sum(a), up to 10^5 * 10^9 = 10^14, so the accumulator must be 64-bit in C, C++ and Java. A 32-bit one wraps to a negative number, that number compares as "inside h", and the search happily returns a speed that does not finish.

The rounding numerator does NOT overflow, and it is worth knowing why rather than assuming either way. Every a[i] is at most 10^9 and k never rises above hi = max(a), which is also at most 10^9, so the largest a + k - 1 can ever be is 1999999999. A 32-bit signed integer holds up to 2147483647, so that expression fits with about seven percent to spare. It fits only because hi is max(a); a looser bound would push it over, which is the real reason to write the whole check in 64 bits and stop thinking about it.

## Related problems

Problem 251 asks for the smallest ship capacity that clears an ordered queue of parcels in D days; same skeleton, different counter. Problem 763 is this problem with a separate deadline on every prefix instead of a single deadline at the end.

## Cost

Time O(n log(max a)). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `n ≤ h ≤ 10^9` - `1 ≤ a[i] ≤ 10^9`