Binary search on the answer

A warehouse must ship parcels in their recorded order over a fixed number of days. It can choose where one day's batch ends, but it cannot split a parcel or move later parcels ahead. The question is the smallest daily weight capacity that can finish the work.

Guessing the batch boundaries directly creates many possibilities. Checking one proposed capacity is much easier: fill a day until the next parcel would exceed it, then start another day.

Choosing a daily shipping capacity

Search capacities, rather than partitions. For a fixed capacity, greedily append the next weight until it would exceed capacity, then start another group. Positive weights make this scan monotone: if a capacity works, every larger one works. The smallest possible capacity is the largest weight; the total weight is always sufficient.

Asking whether a capacity is enough

With weights [2, 3, 4] and two days, capacity 4 needs three batches, while 5 permits [2, 3] | [4]. Any capacity above 5 also works. That false-then-true boundary is what binary search needs. Search between the heaviest parcel and the total weight, keeping a feasible midpoint as a possible answer rather than skipping past it.

Int lo=5,hi=15;
Int mid=lo+(hi-lo)/2; // avoids the overflowing lo+hi formulation

Finding the first capacity that works

A lower-bound search keeps the first feasible value inside [lo,hi], replacing hi with a feasible midpoint and lo with midpoint+1 after failure. Reordering weights would solve a different packing problem. Extra days do not force empty groups or splitting an item. Validate days even when the input is empty; validate every weight before using the bounds. Runtime is O(n log S), where S is the searched capacity range, and each feasibility scan uses constant extra state.

One feasibility check scans n parcels with constant working state. Binary search needs O(log(R+1)) checks across the integer candidate range R, rather than trying every capacity. The range depends on the weight totals, not only the parcel count. Reordering or splitting parcels would change the feasibility problem.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

A larger working capacity would meet the deadline but overstate what the warehouse actually needs.