Bookshelf
Time limit1sMemory limit128 MB
Partition an ordered sequence of books into contiguous shelves to minimize the max of total shelf-height sum and the largest shelf-width, using binary search plus greedy/DP feasibility check.
- Level
Medium7 of 10
- Topics
- Binary search, Greedy, Dynamic programming
- Solved
- No attempts yet
Problem
Chansu has N books numbered from 1 to N. Book i has thickness ti and height hi. The books must be placed on the bookshelf in increasing order of their numbers, and their order cannot be changed.
Books are placed from the bottom shelf upward. On one shelf, books are placed from left to right in increasing order. Once Chansu starts placing books on a higher shelf, he cannot go back down to place more books on a lower shelf.
The height of a shelf is the maximum height of any book on that shelf. The total height H used by the bookshelf is the sum of the heights of all shelves that contain books. The width of a shelf is the sum of the thicknesses of the books on it, and the bookshelf width L is the maximum shelf width. Ignore the thickness of the wood used to build the bookshelf.
After all books are placed, Chansu wants to minimize max(H, L). Find the minimum possible value.
Input
The first line contains the number of books N.
Each of the next N lines contains two integers ti and hi, the thickness and height of one book, given in book-number order.
Output
Print one integer: the minimum possible value of max(H, L), where H is the total bookshelf height and L is the bookshelf width after all books are placed.
Constraints
- 1 <= N <= 100,000
- 1 <= ti, hi <= 10,000