A student is preparing for a test from Amazon Academy for a scholarship.
The student is required to completely read n chapters for the test, where the i-th chapter has pages[i] pages.
The chapters are arranged in increasing order of the index.
Each day the student can either read till the end of a chapter or at most x pages, whichever is minimum. The number of pages remaining to read decreases by x in the latter case.
For example, if pages = [5, 3, 4] and x = 4:
- Day 1: The student reads 4 pages of the first chapter – pages remaining =
[1, 3, 4] - Day 2: The student can only read till the end of the first chapter – pages remaining =
[0, 3, 4] - Day 3: The student can read either till the end of the chapter or
x = 4pages. Since3 < 4, the student reads till the end of the second chapter – pages remaining =[0, 0, 4] - Day 4: The student reads all the 4 pages of the last chapter – pages remaining =
[0, 0, 0]
The test will be given in days number of days from now.
Find the minimum number of pages x that the student should read each day to finish all chapters within days days.
Complete the minimumNumberOfPages function below.
The function is expected to return an integer.
The function accepts the following parameters:
INTEGER_ARRAY pagesINTEGER days
这道题的关键是把“每天读 x 页能否在 days 天内读完”转化为一个单调判定问题：如果 x 可以完成任务，那么更大的 x 也一定可以，因此可以用二分答案搜索最小可行值。对于给定的 x，只需统计把每章页数 pages[i] 按“每次最多读 x 页”拆分后总共需要多少天，即 <code>sum(ceil(pages[i] / x))</code>；若总天数不超过 days，则说明 x 可行。若章节数本身就大于 days，因为每章至少需要一天，直接返回 -1。该题数据范围较大，适合用 <code>O(n log M)</code> 的二分 + 线性检查，其中 <code>M</code> 为页数上界。
