本文共 1911 字，大约阅读时间需要 6 分钟。

437. 书籍复印

描述

给定 n 本书, 第 i 本书的页数为 pages[i]. 现在有 k 个人来复印这些书籍, 而每个人只能复印编号连续的一段的书, 比如一个人可以复印 pages[0], pages[1], pages[2], 但是不可以只复印 pages[0], pages[2], pages[3] 而不复印 pages[1].

所有人复印的速度是一样的, 复印一页需要花费一分钟, 并且所有人同时开始复印. 怎样分配这 k 个人的任务, 使得这 n 本书能够被尽快复印完?

返回完成复印任务最少需要的分钟数.

• 书籍页数总和小于等于2147483647

样例 1：

输入: 	pages = [3, 2, 4], k = 2输出: 	5解释: 	第一个人复印前两本书, 耗时 5 分钟. 第二个人复印第三本书, 耗时 4 分钟.

样例 2：

输入: 	pages = [3, 2, 4], k = 3输出: 	4解释: 	三个人各复印一本书.

挑战

时间复杂度 O(nk)

题解

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 max = 0;        // 最少的情况是每个人复印一本，所以最少需要花费那本页数最大的时间        int min = 0;        for (int page : pages) {
               max += page;            min = Math.max(min, page);        }        // 根据人数可以算出平均复制页数，或者说平均花费时间，而最终无论怎么分配，时间至少等于平均时间        min = Math.max(min, (max + k - 1) / k);		// 二分查找法找到最佳点        int low  = min;        int high = max;        while (low <= high) {
               int mid = (low + high) >>> 1;            boolean ok = true;            // 贪心算法计算按照给定时间至少需要几个人            int time = mid;            // 需要人数            int ps   = 1;            for (int page : pages) {
                   if (page > time) {
                       time = mid;                    ++ps;                    if (ps > k) {
                           ok = false;                        break;                    }                }                if (page < time) {
                       time -= page;                }            }            if (ok) {
                   high = mid - 1;            } else {
                   low = mid + 1;            }        }        return low;    }}

最后说两句

非常感谢你阅读本文章，如果你觉得本文对你有所帮助，请留下你的足迹，点个赞，留个言，多谢~

作者水平有限，如果文章内容有不准确的地方，请指正。

希望小伙伴们都能每天进步一点点。

声明

本文由博客原创，转载请注明来源，谢谢~

转载地址：https://le-yi.blog.csdn.net/article/details/114287625 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！