Overview

We arrange books in order while respecting the width limit of each shelf tier, and determine the required number of tiers.

Analysis

This problem can be efficiently solved using a greedy approach.

The key point is the condition for determining “whether the next book can be placed on the current tier.” To place another book on a tier that already has books, a 1cm gap is required between them, so “current tier’s used width \(+\) 1 (gap) \(+\) thickness of the next book” must fit within the tier width \(W\).

In other words: - When the current tier’s used width is \(0\), the next book can be placed unconditionally. - Otherwise, if \(current\_width + 1 + L[i] \leq W\), place it on the same tier; if it exceeds, place it on the next tier.

A naive approach would be to simulate managing the books in a 2D manner, but since the number of books \(N\) can be up to \(10^6\) and the tier width \(W\) can be up to \(10^9\), this is impractical from the perspective of memory and computation time.

Instead, by only tracking “the current tier’s used width” and “the number of tiers in use,” we can count the required number of tiers while processing all books in order.

Algorithm

1. Set variable shelves (number of tiers in use) to an initial value of \(1\).
2. Set variable current_width (width used on the current tier) to an initial value of \(0\).
3. For each book \(L_i\), perform the following:
   • If current_width == 0, place the book at the beginning of the current tier (no gap needed).
     • current_width += L[i]
   • Otherwise:
     • If current_width + 1 + L[i] <= W, place it on the same tier.

          - `current_width += 1 + L[i]`
       

     • Otherwise, move to a new tier.

          - `shelves += 1`
          - `current_width = L[i]`
       

4. Output the final value of shelves.

Example

Input:

5 10
3 4 2 1 5

Processing flow: - Place the 3cm book on the first tier → width: 3 - Next book 4cm → 3 + 1 + 4 = 8 (OK) → width: 8 - Next book 2cm → 8 + 1 + 2 = 11 (NG) → move to a new tier, width: 2 - Next book 1cm → 2 + 1 + 1 = 4 (OK) → width: 4 - Next book 5cm → 4 + 1 + 5 = 10 (OK) → width: 10

Total number of tiers: 2

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• Accurately manage “the current tier’s used width.”

• Note that the first book can be placed without a gap.

• Correctly handle conditional branching, and reset current_width when moving to a new tier.

  Source Code

N, W = map(int, input().split())
L = list(map(int, input().split()))

shelves = 1
current_width = 0

for i in range(N):
    if current_width == 0:
        current_width += L[i]
    else:
        if current_width + 1 + L[i] <= W:
            current_width += 1 + L[i]
        else:
            shelves += 1
            current_width = L[i]

print(shelves)

---

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