Description

Given n books and the i th book has A[i]pages. You are given_k_people to copy the_n_books.

_n_books list in a row and each person can claim a continous range of the_n_books. For example one copier can copy the books from_i_th to_j_th continously, but he can not copy the 1st book, 2nd book and 4th book (without 3rd book).

They start copying books at the same time and they all cost 1 minute to copy 1 page of a book. What's the best strategy to assign books so that the slowest copier can finish at earliest time?

Example

Given array A =[3,2,4], k =2.

Return 5( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )

Solution

这题用传统DP来做就显得很蠢了，因为要搞一个m*n的数组，动态方程是dp[i][j] = dp[k][j - 1] + (A[k] + ... + A[i - 1]), k取值范围从1到i。complexity n^2*m

所以巧妙一点用二分法。为什么可以用二分法呢，因为一个人最少翻的页数是max of pages array，为啥呢，因为他至少要把一本书饭碗吧，最多翻的页数是其他所有人都不干活只有这一个人干活把所有书都翻完，所以是sum of pages array。要在这个min，max之前找一个合适的点，是k个人刚好能翻完的页数。做一个copyBooksHelper用来算每个人至多翻固定页数，最少需要的人数。用这个结果来二分就好啦

public class Solution {
    /*
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        // write your code here
        if (pages == null || pages.length == 0 || k <= 0) {
            return 0;
        }


        int start = 0;
        int end = 0;
        for (int page : pages) {
            start = Math.max(start, page);
            end += page;
        }

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int count = copyBooksHelper(pages, mid);
            if (count <= k) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (copyBooksHelper(pages, start) <= k) {
            return start;
        } 

         return end;
    }

    public int copyBooksHelper(int[] pages, int page) {
        int count = 0;
        int sum = 0;
        for (int p : pages) {
            if (sum + p > page) {
                sum = 0;
                count++;
            }

            sum += p;
        }

        return sum == 0 ? count : count + 1;
    }
}