一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 261|回复: 7
收起左侧

[算法题] copy books binary search 解法

[复制链接] |试试Instant~ |关注本帖
John.Tan 发表于 2016-11-28 05:14:29 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 John.Tan 于 2016-11-28 05:17 编辑

https://www.lintcode.com/en/problem/copy-books/
我把copy books 这题写了,我只能做出O(k * n^2) 的解, 用了2000+ms 跑完,网上有个大神写了个binary search的解,我跑了只要9ms!!。我看不大懂他写的valid()函数,请指点我一下,感激不尽
    int copyBooks(vector<int> &pages, int k) {
        if (k >= pages.size()) {
            return *max_element(pages.cbegin(), pages.cend());
        }

        int sum = 0;
        for (const auto& page : pages) {
            sum += page;
        }
        int average = sum / k;   // Lower bound.
        return binarySearch(pages, k, average, sum);
    }

    int binarySearch(const vector<int> &pages,
                     const int k, int left, int right) {
        while (left <= right) {
            const auto mid = left + (right - left) / 2;
            if (valid(pages, k, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // Check whether everyone copying at most x pages works or not.
    bool valid(const vector<int> &pages, const int k, const int x) {
        int sum = 0;
        int people = 0;
        for (int i = 0; i < pages.size() && people < k; ++i) {
            if (sum + pages > x) {
                sum = 0;
                ++people;
            }
            sum += pages;
        }
        return  people < k && sum <= x;
    }


Eddyz 发表于 2017-1-4 18:51:43 | 显示全部楼层
大概是这个意思(仅供参考):

1、计算所有的工作小时数( Sum ),然后除以 K 求平均数(A)。
2、验证。如果单人最大值是 A 的话,就返回 A
     2.1 A 的值只能增加,不会减小。
     2.2 A 的值每加 1 即去验证:是否所有人都在 A 的范围内,相加是否在 Sum 范围内。

个人感觉那个 binarySearch() 感觉名字有点迷惑人,这可不是二分查找算法,因为没有找。而是二分计算后递增。叫: binaryDivide() 或 binaryIncreament() 比较合适。
回复 支持 反对

使用道具 举报

Eddyz 发表于 6 天前 | 显示全部楼层
题意:按顺序给你N个数,将这N个数分成连续的M段,使得这M段每段的和中的最大值最小,输出最小值(1<=N<=100000,1<=M<=N,每个数在1到10000之间),如果有多种可能的话,尽量在前面进行划分。

思路:

1、由于函数具有单调性的特征,因此可以用二分枚举的办法去实现它,但这里不需要排序。

2、输出的时候需要用到贪心的思想,既尽量往前划分。

3、大概的思路就是二分枚举求得满足题意的最大值之后,然后以这个最大值通过从后往前的方式划分成段,如果剩余可划分段与i+1的值相等(尽量靠前),则将剩余的段往前划分,具体实现可以用一个标记数组表示是否划分。

5、注意要用long long 来存。

解题思路借鉴了大神的,感觉这个思路比较清晰、易懂,希望能够帮助到博友们


  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int maxm = 500 + 5;
  6. int m, k, p[maxm];
  7. int solve(long long maxp)
  8. {
  9.   long long done = 0;
  10.   int ans = 1;
  11.   for(int i = 0; i < m; i++)
  12.     {
  13.     if(done + p[i] <= maxp) done += p[i];
  14.     else { ans++; done = p[i]; }
  15.     }
  16.   return ans;
  17. }
  18. int last[maxm];
  19. void print(long long ans)
  20. {
  21.   long long done = 0;
  22.   memset(last, 0, sizeof(last));
  23.   int remain = k;
  24.     for(int i = m-1; i >= 0; i--)
  25.     {
  26.     if(done + p[i] > ans || i+1 < remain)
  27.        {    last[i] = 1; remain--; done = p[i];    }
  28.     else
  29.       done += p[i];
  30.     }
  31.     for(int i = 0; i < m-1; i++)
  32.     {
  33.     printf("%d ", p[i]);
  34.     if(last[i]) printf("/ ");
  35.     }
  36.     printf("%d\n", p[m-1]);
  37. }
  38. int main()
  39. {
  40.   int T;
  41.   scanf("%d", &T);
  42.   while(T--)
  43.   {
  44.     scanf("%d%d", &m, &k);
  45.     long long tot = 0;
  46.     int maxp = -1;
  47.     for(int i = 0; i < m; i++)
  48.     {
  49.       scanf("%d", &p[i]);
  50.       tot += p[i];
  51.       maxp = max(maxp, p[i]);
  52.     }
  53.     long long L = maxp, R = tot;
  54.     while(L < R)
  55.     {
  56.       long long M = L + (R-L)/2;
  57.       if(solve(M) <= k) R = M; else L = M+1;
  58.     }
  59.     print(L);
  60.   }
  61.   return 0;
  62. }
复制代码



转载: http://www.cnblogs.com/www-cnxcy-com/p/4702312.html
回复 支持 反对

使用道具 举报

Eddyz 发表于 6 天前 | 显示全部楼层
使用二分枚举法:把优化问题转化为判定问题。
  1.     /**
  2.     http://blog.csdn.net/shuangde800/article/details/7828695
  3.      
  4.         分析与总结:
  5.         所化的总时间取决于所有抄写员中任务最多的那个,是经典的最大值最小化问题。
  6.     LRJ《算法入门经典》P151页有介绍:
  7.    
  8.         二分最小值x,把优化问题转化为判定问题。
  9.         设为P(x)。
  10.         设所有数之和为M,则二分次数为O(logM)。
  11.         计算P(x)的时间的时间复杂度为:O(n),//逐一验证
  12.         因此总时间复杂度为:O(nlogM)
  13.      */
复制代码



  1.     int copyBooks(vector<int> &pages, int k) {
  2.         if (k >= pages.size()) {
  3.             return *max_element(pages.cbegin(), pages.cend());
  4.         }

  5.         int sum = 0;
  6.         for (const auto& page : pages) {
  7.             sum += page;
  8.         }
  9.         int average = sum / k;   // Lower bound.
  10.         return binarySearch(pages, k, average, sum);
  11.     }

  12.     //用二分枚举法,逐一验证所枚举的数是否符合要求。
  13.     int binarySearch(const vector<int> &pages,
  14.                      const int k, int left, int right) {
  15.         while (left <= right) {
  16.             const auto mid = left + (right - left) / 2; //二分枚举
  17.             if (valid(pages, k, mid)) {
  18.                 right = mid - 1;
  19.             } else {
  20.                 left = mid + 1;
  21.             }
  22.         }
  23.         return left;
  24.     }


  25.     //验证:
  26.     //在给定最小花费时间是x的情况下,计算所需的人数(people)。
  27.     //如果 people 的值比 k 小,说明 x 设大了
  28.     //如果 people 的值比 k 大,说明 x 设小了
  29.     bool valid(const vector<int> &pages, const int k, const int x) {
  30.         int sum = 0;
  31.         int people = 0;
  32.         for (int i = 0; i < pages.size() && people < k; ++i) {
  33.             if (sum + pages > x) {
  34.                 sum = 0;
  35.                 ++people;
  36.             }
  37.             sum += pages;
  38.         }
  39.         return  people < k && sum <= x;
  40.     }
复制代码

回复 支持 反对

使用道具 举报

Eddyz 发表于 6 天前 | 显示全部楼层
讨论:

1、 int average = sum / k;   // Lower bound.
该值应该设为 所有元素中最大的那个。因为不可能比最大的值小。而不是所有值的平均值。

2、
if (valid(pages, k, mid)) {
    right = mid - 1;
} else {
    left = mid + 1;
}

right 和 left 每次步长是 1,是否递增的太慢?
还是根据已求得的 average,判定最小最大值就在 average 附近?



-
回复 支持 反对

使用道具 举报

Eddyz 发表于 6 天前 | 显示全部楼层
附其它解法,以供参考:


  1. /**
  2. * www.jiuzhang.com/solutions/copy-books/
  3. *
  4. * 本代码由九章算法编辑提供。版权所有,转发请注明出处。
  5. * - 九章算法致力于帮助更多中国人找到好的工作,教师团队均来自硅谷和国内的一线大公司在职工程师。
  6. * - 现有的面试培训课程包括:九章算法班,系统设计班,算法强化班,Java入门与基础算法班,Android 项目实战班,Big Data 项目实战班,
  7. * - 更多详情请见官方网站:http://www.jiuzhang.com/?source=code
  8. */

  9. // version 1: Binary Search
  10. // this version cost O(n log m) where n is the number of books and m is the sum of the pages.
  11. public class CopyBooks {
  12.     /**
  13.      * @param pages: an array of books with pages number.
  14.      * @param k: number of copiers.
  15.      * @return: minimum max number.
  16.      */
  17.     public int copyBooks(int[] pages, int k) {
  18.         if (pages.length == 0) {
  19.             return 0;  
  20.         }
  21.         
  22.         //1. calculate the sum of pages, and its max element.
  23.         int sum = 0;
  24.         int biggest = pages[0];
  25.         for (int i = 0; i < pages.length; i++) {
  26.             sum += pages[i];
  27.             biggest = Math.max(biggest, pages[i]);
  28.         }
  29.         
  30.         //2.
  31.         int midStart = biggest;
  32.         int end = sum;        
  33.         while (midStart + 1 < end) {
  34.             int mid = midStart + (end - midStart) >> 1;
  35.             // validate if the mid value can meet with k copiers.
  36.             if (calculateCopiers(pages, mid) > k) { // when meet. midStart value is smaller.
  37.                 midStart = mid;                     // increase it.
  38.             } else {
  39.                 end = mid;                          // when can't meet. midStart value is larger.
  40.             }
  41.         }
  42.         
  43.         if (calculateCopiers(pages, midStart) <= k) {
  44.             return midStart;
  45.         }
  46.         
  47.         return end;
  48.     }
  49.    
  50.    
  51.    
  52.    
  53.     private int calculateCopiers(int[] pages, int limit) {
  54.         if (pages.length == 0) {
  55.             return 0;
  56.         }
  57.         
  58.         int copiers = 1;
  59.         int subTaskSum = pages[0]; // limit is always >= pages[0]
  60.         for (int i = 1; i < pages.length; i++) {
  61.             if (subTaskSum + pages[i] > limit) {
  62.                 copiers++;
  63.                 subTaskSum = 0;
  64.             }
  65.             subTaskSum += pages[i];
  66.         }
  67.         
  68.         return copiers;
  69.     }
  70.    
  71.     /**
  72.     public static void main(String[] args) {
  73.         int[] pages = new int[]{};
  74.     }
  75.     */
  76. }

复制代码
回复 支持 反对

使用道具 举报

Eddyz 发表于 6 天前 | 显示全部楼层
另附参考算法:(个人已验证)

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

  7.     二分最小值x,把优化问题转化为判定问题。
  8.     设为P(x)。
  9.     设所有数之和为M,则二分次数为O(logM)。
  10.     计算P(x)的时间的时间复杂度为:O(n),//逐一验证
  11.     因此总时间复杂度为:O(nlogM)
  12. */  
  13. /**===================================================================================*/  
  14. /**
  15. * www.jiuzhang.com/solutions/copy-books/
  16. *  
  17. * 本代码由九章算法编辑提供。版权所有,转发请注明出处。
  18. * - 九章算法致力于帮助更多中国人找到好的工作,教师团队均来自硅谷和国内的一线大公司在职工程师。
  19. * - 现有的面试培训课程包括:九章算法班,系统设计班,算法强化班,Java入门与基础算法班,
  20. *   Android 项目实战班,Big Data 项目实战班,
  21. * - 更多详情请见官方网站:http://www.jiuzhang.com/?source=code
  22. */  
  23.   
  24. // version 1: Binary Search  
  25. // this version cost O(n log m) where n is the number of books and m is the sum of the pages.  
  26. public class CopyBooks {  
  27.     /**
  28.      * @param pages: an array of books with pages number.
  29.      * @param k: number of copiers.
  30.      * @return: minimum max number.
  31.      */  
  32.     public int copyBooks(int[] pages, int k) {  
  33.         if (pages.length == 0) {  
  34.             return 0;   
  35.         }  
  36.          
  37.         //1. calculate the sum of pages, and its max element.  
  38.         int sum = 0;  
  39.         int biggest = pages[0];  
  40.         for (int i = 0; i < pages.length; i++) {  
  41.             sum += pages[i];  
  42.             biggest = Math.max(biggest, pages[i]);  
  43.         }  
  44.          
  45.         //2.use binary enumeration to calculate whether the mid   
  46.         //  value is the proper one.  
  47.         int midStart = biggest;  
  48.         int end = sum;         
  49.         while (midStart + 1 < end) {  
  50.             int mid = midStart + ((end - midStart) >> 1); // binary enumeration.  
  51.             // validate if the mid value can meet with k copiers.  
  52.             if (calculateCopiers(pages, mid) > k) { // when meet. midStart value is smaller.   
  53.                 midStart = mid;            // increase it.   
  54.             } else {  
  55.                 end = mid;                 // when can't meet. midStart value is larger.  
  56.             }  
  57.         }  
  58.          
  59.         if (calculateCopiers(pages, midStart) <= k) {  
  60.             return midStart;  
  61.         }  
  62.          
  63.         return end;  
  64.     }  
  65.       
  66.       
  67.       
  68.     // with given limit number, calculate the copiers that needed.  
  69.     private int calculateCopiers(int[] pages, int limit) {  
  70.         if (pages.length == 0) {  
  71.             return 0;  
  72.         }  
  73.          
  74.         int copiers = 1;  
  75.         int subTaskSum = pages[0]; // limit is always >= pages[0]  
  76.         for (int i = 1; i < pages.length; i++) {  
  77.             if (subTaskSum + pages[i] > limit) {  
  78.                 copiers++;  
  79.                 subTaskSum = 0;  
  80.             }  
  81.             subTaskSum += pages[i];  
  82.         }  
  83.          
  84.         return copiers;  
  85.     }   
  86. }
复制代码



测试用例:

  1.     @Test
  2.     public void testCopy() {
  3.         int[] pages = new int[]{100, 200, 300, 413, 321, 500};
  4.         
  5.         
  6.         CopyBooks c = new CopyBooks();
  7.         
  8.         int minimumMax = c.copyBooks(pages, 2);
  9.         
  10.         System.out.println(minimumMax);
  11.         
  12.     }
复制代码



回复 支持 反对

使用道具 举报

衣领子 发表于 昨天 02:06 | 显示全部楼层
照着九章大神的代码改写了一个自己好理解的

public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: an integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        if (pages.length == 0) {
            return 0;  
        }
        
        int total = 0;
        int max = pages[0];
        for (int i = 0; i < pages.length; i++) {
            total += pages[i];
            if (max < pages[i]) {
                max = pages[i];
            }
        }
        
        int start = max;
        int end = total;
        
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            // 假设 k 人数 = pages.length(每个人同时复印一本) 对应 max的值 为max 即range中最小的的start值
            // k 固定, 若能copy,mid 作为max的值, 就提高此max值试试
            if (ifCanCopy(pages, mid, k)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        // 求最小,先看最小
        if (ifCanCopy(pages, start, k)) {
            return start;
        }
        
        return end;
    }
   
    private boolean ifCanCopy(int[] pages, int limit, int k) {
        if (pages.length == 0) {
            return true;
        }

        int copiers = 1;
        int sum = pages[0]; // limit is always >= pages[0]
        for (int i = 1; i < pages.length; i++) {
            if (sum + pages[i] > limit) {
                copiers++;
                sum = 0;
            }
            sum += pages[i];
        }
        // means can finish it with <= k ppl.
        if (copiers <= k) {
            return true;
        } else {
            return false;
        }
    }
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-19 08:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表