Algorithm之二分枚举之copy books

copy books

Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.

由书法家誊写作家的书，然后出版。


1、题目

    
    /**
     https://www.lintcode.com/en/problem/copy-books/
     
     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 continuous range of the n books. 
     For example one copier can copy the books from i-th to j-th continuously, 
     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. )
    
     :::Challenge:::
     Could you do this in O(n*k) time ?


     
     *
     */
    

    

解法：

/**
  http://blog.csdn.net/shuangde800/article/details/7828695
 
    分析与总结：
    所化的总时间取决于所有抄写员中任务最多的那个，是经典的最大值最小化问题。
    LRJ《算法入门经典》P151页有介绍：

    二分最小值x，把优化问题转化为判定问题。
    设为P(x)。
    设所有数之和为M，则二分次数为O(logM)。
    计算P(x)的时间的时间复杂度为：O(n)，//逐一验证
    因此总时间复杂度为：O(nlogM)
 */
/**===================================================================================*/
/**
 * www.jiuzhang.com/solutions/copy-books/
 * 
 * 本代码由九章算法编辑提供。版权所有，转发请注明出处。
 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
 * - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，
 *   Android 项目实战班，Big Data 项目实战班，
 * - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
 */

// version 1: Binary Search
// this version cost O(n log m) where n is the number of books and m is the sum of the pages.
public class CopyBooks {
    /**
     * @param pages: an array of books with pages number.
     * @param k: number of copiers.
     * @return: minimum max number.
     */
    public int copyBooks(int[] pages, int k) {
        if (pages.length == 0) {
            return 0;  
        }
        
        //1. calculate the sum of pages, and its max element.
        int sum = 0;
        int biggest = pages[0];
        for (int i = 0; i < pages.length; i++) {
            sum += pages[i];
            biggest = Math.max(biggest, pages[i]);
        }
        
        //2.use binary enumeration to calculate whether the mid 
        //  value is the proper one.
        int midStart = biggest;
        int end = sum;        
        while (midStart + 1 < end) {
            int mid = midStart + ((end - midStart) >> 1); // binary enumeration.
            // validate if the mid value can meet with k copiers.
            if (calculateCopiers(pages, mid) > k) { // when meet. midStart value is smaller. 
                midStart = mid;            // increase it. 
            } else {
                end = mid;                 // when can't meet. midStart value is larger.
            }
        }
        
        if (calculateCopiers(pages, midStart) <= k) {
            return midStart;
        }
        
        return end;
    }
    
    
    
    // with given limit number, calculate the copiers that needed.
    private int calculateCopiers(int[] pages, int limit) {
        if (pages.length == 0) {
            return 0;
        }
        
        int copiers = 1;
        int subTaskSum = pages[0]; // limit is always >= pages[0]
        for (int i = 1; i < pages.length; i++) {
            if (subTaskSum + pages[i] > limit) {
                copiers++;
                subTaskSum = 0;
            }
            subTaskSum += pages[i];
        }
        
        return copiers;
    }
    
    /**
    public static void main(String[] args) {
        int[] pages = new int[]{};
    }
    */
}

-