Overview

This is a problem where books are placed from left to right on shelves with gaps between them, and we need to find the required number of shelves. Books are placed so that they do not exceed the width of each shelf.

Analysis

This can be solved by simulating according to the rules of the problem. The key point is that when there are already books on the current shelf, a 1-centimeter gap is required when placing the next book. A straightforward approach of simply managing the shelves by checking the current shelf’s width for each book is sufficient. Although the constraint \(N \leq 10^6\) is large, it can be processed efficiently since it only requires a single loop.

Algorithm

1. Initialize the current shelf width current_width and the number of shelves stages (starting from 1 shelf).
2. Process each book in order:
   • If there are no books on the current shelf (current_width == 0), place the book at the left edge of the current shelf and set current_width to the thickness of that book.
   • If there are books on the current shelf, check whether the current shelf width plus a 1-centimeter gap plus the next book’s thickness is less than or equal to the shelf width \(W\).
     • If it does not exceed: update the current shelf width (current_width + 1 + L[i]) and place the book on the same shelf.
     • If it exceeds: move to a new shelf (increment stages by 1) and reset the current shelf width to the new book’s thickness.
3. After placing all books, output the number of shelves stages.

Complexity

• Time complexity: \(O(N)\)
  • Because we process all \(N\) books in a single loop.
• Space complexity: \(O(N)\)
  • Because the list storing the thicknesses of the books has size \(N\).

Implementation Notes

• Whether the current shelf width is 0 determines if it is the first book on the shelf.

• To account for gaps, when placing the second book onward, the check uses current_width + 1 + L[i].

• The implementation uses a simple loop to handle efficiently even when input values are large.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    W = int(data[1])
    L = list(map(int, data[2:2+n]))
    
    current_width = 0
    stages = 1
    
    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:
                stages += 1
                current_width = L[i]
                
    print(stages)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.