描述
给出一个数组A包含n个元素，表示n本书以及各自的页数。现在有个k个人复印书籍， 每个人只能复印连续一段编号的书，比如A[1],A[2]由第一个人复印，但是不能A[1], A[3]由第一个人复印，求最少需要的时间复印所有书。
样例
A = [3,2,4]，k = 2，返回5，第一个人复印前两本书
代码
- 二分法
// 数组代表工作量，令数组所有的子数组中和最大的那个子数组的值尽可能小，即让所有人中工作量最大的那个最小
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 == null || pages.length == 0) {
return 0;
}
int max = pages[0];
int total = 0;
for (int i = 0; i < pages.length; i++) {
total += pages[i] ;
if (pages[i] > max) {
max = pages[i];
}
}
// 对每个人工作量进行二分判断
int start = max;
int end = total;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (countCopier(pages, mid) > k) {
start = mid;
// 等于 k 的情况尽可能往前查找，才会让每个人的工作量尽可能小
} else {
end = mid;
}
}
// 因为目标是工作量尽可能小，所以先检查 start
if (countCopier(pages, start) <= k) {
return start;
} else {
return end;
}
}
// 计算当前每个人这么大工作量需要的人数
// limit 代表当前每个人工作量
private int countCopier(int[] pages, int limit) {
if (pages.length == 0) {
return 0;
}
int sum = pages[0];
int copier = 1;
for (int i = 1; i < pages.length; i++) {
// 超过每人工作量后人数加 1
if (sum + pages[i] > limit) {
copier++;
sum = 0;
}
// sum = 0 执行完后又继续执行下行代码，只是把上一个人的工作量归 0 了，当前人的工作量把 pages[i] 加上
// 没超过工作量
sum += pages[i];
}
return copier;
}
}
- 动态规划
// version 2: Dynamic Programming
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
if(pages == null){
return 0;
}
int n = pages.length;
if (n == 0){
return 0;
}
if (k > n) {
k = n;
}
int[] sum = new int[n];
sum[0] = pages[0];
for (int i = 1; i < n; ++i) {
sum[i] = sum[i-1] + pages[i];
}
int[][] f = new int[n][k];
for (int i=0; i<n; ++i) f[i][0] = sum[i];
for (int j=1; j<k; ++j) {
int p = 0;
f[0][j] = pages[0];
for (int i = 1; i < j; ++i) f[i][j] = Math.max(f[i-1][j], pages[i]);
for (int i = j; i < n; ++i) {
while (p < i && f[p][j-1] < sum[i] - sum[p]) ++p;
f[i][j] = Math.max(f[p][j - 1], sum[i] - sum[p]);
if (p > 0) {
--p;
}
f[i][j] = Math.min(f[i][j], Math.max(f[p][j - 1], sum[i] - sum[p]));
}
}
return f[n - 1][k - 1];
}
}
- 动态规划专题班版本
public class Solution {
/**
* @param pages: an array of integers
* @param k: an integer
* @return: an integer
*/
public int copyBooks(int[] A, int K) {
int n = A.length;
if (n == 0) {
return 0;
}
int i, j, k, sum;
int[][] f = new int[2][n + 1];
int old, now = 0;
for (i = 0; i <= n; ++i) {
f[now][i] = Integer.MAX_VALUE;
}
f[now][0] = 0;
for (i = 1; i <= K; ++i) {
old = now;
now = 1 - now;
for (j = 0; j <= n; ++j) {
f[now][j] = Integer.MAX_VALUE;
sum = 0;
for (k = j; k >= 0; --k) {
if (f[old][k] < Integer.MAX_VALUE) {
f[now][j] = Math.min(f[now][j], Math.max(sum, f[old][k]));
}
if (k > 0) {
sum += A[k - 1];
}
}
}
}
return f[now][n];
}
}
