Description

Given n books and the ith 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 ith to jth 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?

中文描述：
給出一個(gè)數(shù)組A包含n個(gè)元素，表示n本書以及各自的頁數(shù)?，F(xiàn)在有個(gè)k個(gè)人復(fù)印書籍，每個(gè)人只能復(fù)印連續(xù)一段編號(hào)的書，比如A[1],A[2]由第一個(gè)人復(fù)印，但是不能A[1],A[3]由第一個(gè)人復(fù)印，求最少需要的時(shí)間復(fù)印所有書。

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. )

解題思路：
這道題和wood cut 一樣 屬于相同類型的題， wood cut需要找到最大值 而這里需要找到最小值。 因此我們?nèi)匀皇怯枚址▉碜?。那么首先?最小值應(yīng)該是0， 因?yàn)橛锌赡軅魅氲臄?shù)組是空數(shù)組，也就是沒有書， 那么需要的復(fù)印時(shí)間最小就為0. 那么最大值呢？最大值理論上應(yīng)該是數(shù)組里面的所有數(shù)據(jù)加起來之和。 也就是全部書都拿給一個(gè)人復(fù)印， 由于多人復(fù)印時(shí)間是并行的， 那么一個(gè)人把所有書都復(fù)印完肯定是最長(zhǎng)的時(shí)間。 但是由于不確定輸入數(shù)據(jù) 遍歷一遍數(shù)組求和其實(shí)沒有必要，所以最大值姑且賦一個(gè)Integer.MAX_VALUE就好。

代碼：

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
            int min = 0, max = Integer.MAX_VALUE;
            while(min + 1 < max)
            {
                int mid = min + (max - min) / 2;
                if(check(pages, mid, k))
                {
                    max = mid;
                }else
                    min = mid;
            }

            if(check(pages, min, k))
                return min;
            return max;

        }

        public boolean check(int[] pages, int limit, int k)
        {
            int num = 0;
            int left = 0;

            for(int item : pages)
            {
                if(item > limit)
                    return false;
                if(item > left)
                {
                    num++;
                    left = limit;
                }
                left -= item;
            }

            return num <= k;
        }
    }

判斷條件： 猜測(cè)的復(fù)印時(shí)間應(yīng)該是一個(gè)人的復(fù)印時(shí)間限制， 如果數(shù)組中有一個(gè)數(shù)據(jù)的值大于這個(gè)時(shí)間限制。說明是不可能在這個(gè)時(shí)間內(nèi)復(fù)印完的 直接返回false。num用來記錄可能的需要復(fù)印的人數(shù)， 而left則表示每個(gè)人剩余的復(fù)印時(shí)間， 如果書的頁數(shù)大于一個(gè)人所剩余的復(fù)印時(shí)間， 那么說明還需要多一個(gè)人來復(fù)印這本書， 然后num加1， left重置為limit之后再減去item，留給下一次接著判斷。 最后 如果num小于等于k， 說明這個(gè)時(shí)間可行， 那么改變max， 反之改變min。 最后檢查min是否滿足條件（檢查min是因?yàn)榍蟮氖亲钚≈担?，若是滿足條件直接返回，不滿足就返回max。