B - Bin-ary Packing Editorial by evima
Let \(W\) be the total weight of the packages.
Binary search on the answer, and determine whether it is possible to make the weight of every bag at most \(X\).
Consider the packages in decreasing order of weight. When focusing on packages of weight \(2^i\), a bag with remaining capacity \(C\) may be split into the following two kinds of bags.
- \(\lfloor C/2^i \rfloor\) bags of capacity \(2^i\)
- \(1\) bag of capacity \(C \bmod 2^i\)
Proof
We show this by induction on $i$.
When $i=0$, this is clear since the weight of all remaining packages is $1$.
Suppose $i \gt 0$. If the original bag contained $k$ packages of weight $2^i$, then $k \le \lfloor C/2^i \rfloor$, so they can still be put in after the split.
The weight of the remaining packages is at most $2^{i-1}$. Whether we split at capacity $2^i$ and then split at $2^{i-1}$, or split directly at $2^{i-1}$, the result is the same, so we can use the induction hypothesis.
The number of distinct capacities is always at most \(2\), so the problem can be solved in \(O(M \log W)\) by simulating while grouping together bags of the same capacity.
posted:
last update: