Overview

A problem of selecting the maximum number of boxes that can be stacked from \(N\) cardboard boxes while satisfying the load capacity constraints.

Analysis

In this problem, each cardboard box has a weight \(W_i\) and a load capacity \(D_i\). If the total weight of items placed on top of a box exceeds that box’s load capacity, the box gets crushed.

The ordering matters

The order in which boxes are stacked is extremely important. For example, while you might want to place heavy boxes at the bottom, if they have low load capacity, you can’t place much on top of them. Conversely, using light boxes with high load capacity at the bottom may allow stacking more boxes overall.

Here is a key observation:

By sorting based on the value “the box’s own weight \(W_i\) + its maximum load capacity \(D_i\)” for each box \(i\), we can obtain the optimal stacking order.

In other words, sorting by $\( \text{key}_i = W_i + D_i \)$ in ascending order gives us the optimal order for stacking boxes. This is a classic greedy technique.

Why does this work?

When comparing two boxes \(A\) and \(B\): - If \(W_A + D_A \leq W_B + D_B\), then stacking \(A\) first tends to leave more options for later choices.

This can be formally proven, but intuitively, by using boxes with smaller “support limits (= \(W_i + D_i\))” first, we can stack more boxes overall.

Selecting which boxes to include

After sorting, we examine boxes from the front, but simply trying to stack all of them may exceed load capacity limits.

Therefore, we use the strategy of “removing the heaviest box among those currently selected and replacing it with the current lighter box.” This can be efficiently implemented using a max heap.

Specifically: 1. Examine boxes in sorted order. 2. If the current box can be stacked, add it to the heap. 3. If it cannot be stacked, check whether swapping it with the heaviest box in the heap is beneficial, and perform the swap if so.

This ensures we always “maximize the number of usable boxes while minimizing the total weight.”

Algorithm

1. Sort each box \((W_i, D_i)\) in ascending order of \(W_i + D_i\).
2. Using a max heap (in Python, use heapq with negated values to extract the maximum), perform the following:
   • For each box, if the current total weight is within that box’s load capacity, stack it (add to the heap).
   • Otherwise, compare it with the heaviest box in the heap, and swap if doing so is beneficial.
3. The final size of the heap is the answer.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\), and heap operations for each element take at most \(O(\log N)\), giving \(O(N \log N)\) overall.
• Space complexity: \(O(N)\)
  • The heap size is at most \(N\).

Implementation Notes

• Python’s heapq is a min heap, so to extract the maximum value, push/pop negated values.

• When sorting boxes, sort the pairs (w, d) using key=lambda x: x[0] + x[1].

• Maintain total_weight and compare/update it at each step.

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    boxes = []
    index = 1
    for i in range(N):
        w = int(data[index])
        d = int(data[index+1])
        boxes.append((w, d))
        index += 2
    
    # (w_i, d_i) を d_i + w_i の昇順でソート
    boxes.sort(key=lambda x: x[1] + x[0])
    
    # 最大ヒープ（Pythonはmin-heapなので、負の値を入れる）
    heap = []
    total_weight = 0
    
    for w, d in boxes:
        # 現在の箱を積めるか？
        if total_weight <= d:
            heapq.heappush(heap, -w)
            total_weight += w
        else:
            # 積めない場合、一番重い箱を取り除いて代わりに今の箱を入れるか考える
            if heap and -heap[0] > w:
                removed_w = -heapq.heappop(heap)
                total_weight -= removed_w
                total_weight += w
                heapq.heappush(heap, -w)
    
    print(len(heap))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.