leetcode面试题2 抄书问题
http://codevs.cn/problem/3162/
这是经典的求最大值最小的问题，用二分答案。二分一个单人抄书的最大值，然后从后向前让每个人尽可能多抄<不多于二分的值>，若抄完了整本书，则下调上界<即可能人没轮完就取完了>，若还未抄完整本书就轮完了所有人，则上调下界<即还未取满就完了>，当上界=下界时退出，按同样的方法从后往前取书
Read full article from leetcode面试题2 抄书问题
http://codevs.cn/problem/3162/
有n本书和k个抄写员。要求n本书必须连续地分配给这k个抄写员抄写。也就是说前a1本书分给第一个抄写员，接下来a2本书分给第二个抄写员，如此类推（a1,a2需要你的算法来决定）。给定n,k和每本书的页数p1,p2..pn，假定每个抄写员速度一样（每分钟1页），k个抄写员同时开始抄写，问最少需要多少时间能够将所有书全部抄写完工？（提示：本题有很多种算法可以在不同的时间复杂度下解决，需要尽可能的想到所有的方法）
解答
解法1：动态规划
设f[i][j]代表前i本书分给j个抄写员抄完的最少耗时。答案就是f[n][k]。状态转移方程f[i][j] = min{max(f[x][j-1], sum(x+1, i)), j<x<i}。其中x是在枚举第j个抄写员是从哪本书开始抄写。
时间复杂度O(n^2*k)
public int shortestTime(int[] pages, int k) {
int n = pages.length;
int[][] states = new int[k + 1][n + 1];
int[] sums = new int[n + 1];
sums[0] = 0;
sums[1] = pages[0];
states[1][1] = pages[0];
for (int i = 2; i <= n; i++) {
sums[i] = sums[i-1] + pages[i-1];
states[1][i] = sums[i];
//System.out.println(sums[i]);
}
for (int i = 2; i <= k; i++) {
for (int j = 1; j <= n; j++) {
int minVal = Integer.MAX_VALUE;
for (int jj = 0; jj <= j; jj++){
int val = Math.max(states[i-1][j - jj] , sums[j] - sums[j-jj]);
if (val < minVal){
minVal = val;
}
}
states[i][j] = minVal;
}
}
return states[k][n];
}
下面代码是DP：但是没有考虑边界情况只是写来熟悉算法流程。
12 //f[i][j] = min(f[x][j-1]+sum(x+1,i))(j<=x<=i) 13 ///sum[i][j]表示抄写第i到第j本书需要的时间 14 vector<int> book; 15 int dp[100][100]; 16 int sum[100][100]; 17 int fun(int n,int m) 18 { 19 int i,j,k; 20 int mintime=INT_MIN; 21 22 for(i = 0 ; i < n ; ++i) 23 { 24 for(j = i ; j < m ;++j) 25 { 26 for(k = i ; k <= j ; ++k) 27 { 28 sum[i][j]+=book[k]; 29 } 30 } 31 } 32 for(i = 1 ; i <= n ; ++i) 33 dp[i][1] = sum[0][i-1]; 34 for(j = 2 ; j <= m ; ++j) 35 { 36 for(i = j ; i <= n ; ++i) 37 { 38 dp[i][j]= INT_MAX; 39 for(k = j ; k <= i ; ++k) 40 { 41 mintime = max(dp[k][j-1],sum[k][i-1]); 42 dp[i][j] = min(dp[i][j],mintime); 43 } 44 } 45 } 46 return dp[n][m]; 47 }
解法2；动态规划+决策单调。
同上一解法，但在x的枚举上进行优化，设s[i][j]为使得f[i][j]获得最优值的x是多少。有s[i][j+1]>=s[i][j]>=s[i-1][j]。因此x这一层的枚举不再是每次都是n而是总共加起来n。
时间复杂度O(n*k)
解法3：二分答案
二分答案，然后尝试一本本的加进来，加满了就给一个抄写员。看最后需要的抄写员数目是多余k个还是少于k个，然后来决定是将答案往上调整还是往下调整。
时间复杂度O( n log Sum(pi) )
http://blog.csdn.net/csyzcyj/article/details/17332821这是经典的求最大值最小的问题，用二分答案。二分一个单人抄书的最大值，然后从后向前让每个人尽可能多抄<不多于二分的值>，若抄完了整本书，则下调上界<即可能人没轮完就取完了>，若还未抄完整本书就轮完了所有人，则上调下界<即还未取满就完了>，当上界=下界时退出，按同样的方法从后往前取书
int M,K,a[MAX],min1=IMAX,max1=0,x[MAX],y[MAX],ans;
bool check(int x)
{
int sum=0,now=M;
for(int i=K;i>=1;i--)
{
sum=0;
while(sum+a[now]<=x && now>0)
{
sum+=a[now];
now--;
}
if(now==0) return true;
}
return false;
}
void work()
{
int left=min1,right=max1;
while(left<right)
{
int middle=(left+right)/2;
if(check(middle))//说明最大值多了<即可能人没轮完就取完了>
right=middle;
else left=middle+1;//说明最大值少了<即还未取满就完了>
}
ans=left=right;
}
int main()
{
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
scanf("%d%d",&M,&K);
for(int i=1;i<=M;i++)
{
scanf("%d",&a[i]);
min1=min(a[i],min1);
max1+=abs(a[i]);
}
work();
int sum=0,now=M;
for(int i=K;i>=1;i--)
{
sum=0;
y[i]=now;
while(sum+a[now]<=ans && now>=i)
{
sum+=a[now];
now--;
}
x[i]=now+1;
}
for(int i=1;i<=K;i++)
printf("%d %d\n",x[i],y[i]);
return 0;
}
面试官角度：
该问题的考点在于算法能力。需要一定的算法积累，如对动态规划和二分法的算法积累。面试官不一定会需要你答出所有的解法（根据职位要求和招聘名额来看了），但是你答出多少就能够大概知道你在算法能力上的水平是多少。一般来讲至少需要答出动态规划的解法，因为只要稍微做过一点动态规划的训练，都是可以想出来的。
Read full article from leetcode面试题2 抄书问题
