问题详情
有n本书和k个抄写员。要求n本书必须连续地分配给这k个抄写员抄写。也就是说前a1本书分给第一个抄写员，接下来a2本书分给第二个抄写员，如此类推（a1,a2需要你的算法来决定）。给定n,k和每本书的页数p1,p2..pn，假定每个抄写员速度一样（每分钟1页），k个抄写员同时开始抄写，问最少需要多少时间能够将所有书全部抄写完工？（提示：本题有很多种算法可以在不同的时间复杂度下解决，需要尽可能的想到所有的方法）
解答
解法1：动态规划
设f[j]代表前i本书分给j个抄写员抄完的最少耗时。答案就是f[n][k]。状态转移方程f[j] = min{max(f[x][j-1], sum(x+1, i)), j<x<i}。其中x是在枚举第j个抄写员是从哪本书开始抄写。
时间复杂度O(n^2*k)
解法2；动态规划+决策单调。
同上一解法，但在x的枚举上进行优化，设s[j]为使得f[j]获得最优值的x是多少。有s[j+1]>=s[j]>=s[i-1][j]。因此x这一层的枚举不再是每次都是n而是总共加起来n。
时间复杂度O(n*k)
解法3：二分答案
二分答案，然后尝试一本本的加进来，加满了就给一个抄写员。看最后需要的抄写员数目是多余k个还是少于k个，然后来决定是将答案往上调整还是往下调整。
时间复杂度O( n log Sum(pi) )
面试官角度：
该问题的考点在于算法能力。需要一定的算法积累，如对动态规划和二分法的算法积累。面试官不一定会需要你答出所有的解法（根据职位要求和招聘名额来看了），但是你答出多少就能够大概知道你在算法能力上的水平是多少。一般来讲至少需要答出动态规划的解法，因为只要稍微做过一点动态规划的训练，都是可以想出来的。
按解法一的代码如下：有待优化
- package com.itheima;
- public class Main {
- public static void main(String[] args) {
- int n = 6;
- int p = 3;
- // pages.length == n+1,其中pages[0]是自己添加的
- int[] pages = { 0, 1, 100, 23, 46, 78, 41 };
- int[][] dp = new int[n + 1][p + 1];
- // 初始化-- begin
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j <= p; ++j)
- dp[i][j] = Integer.MAX_VALUE;
- for (int i = 1; i <= n; ++i)
- dp[i][1] = dp[i - 1][1] + pages[i];
- for (int j = 1; j <= p; ++j)
- dp[1][j] = pages[1];
- // 初始化-- end
- // 辅助数组sum[i]=pages[1]+pages[2]+...+pages[i]
- int[] sum = new int[n + 1];
- sum[0] = 0;
- for (int i = 1; i <= n; ++i)
- sum[i] = sum[i - 1] + pages[i];
-
- // 核心计算部分
- for (int j = 2; j <= p; ++j) { // 枚举抄书员
- for (int i = 2; i <= n; ++i) { // 枚举书的总数
- dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]);
- for (int x = j - 1; x < i; ++x) { // 枚举第j个人处理的书本数 0 ~ i-j
- dp[i][j] = Math.min(dp[i][j], Math.max(dp[x][j - 1], sum[i] - sum[x]));
- }
- }
- }
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= p; ++j) {
- System.out.print(dp[i][j] + "\t");
- }
- System.out.println();
- }
- System.out.println("结果为" + dp[n][p]);
- }
- }
|
|
收藏
淘帖
踩
