首页 > 学院 > 开发设计 > 正文

Arithmetic problem | 书籍复印

2019-11-11 07:27:07
字体:
来源:转载
供稿:网友

题目如下: 给出一个数组A包含n个元素,表示n本书以及各自的页数。现在有个k个人复印书籍,每个人只能复印连续一段编号的书,比如A[1],A[2]由第一个人复印,但是不能A[1],A[3]由第一个人复印,求最少需要的时间复印所有书。

样例: A = [3,2,4],k = 2

返回5,第一个人复印前两本书

解题思路: 这个题有一定难度,先提出合理假设B(l,k)为l个数据规模的k人分配使用最短时间。把数据规模划分为两部分,从右到左,依次增加右规模,表示第k人印刷书籍量,而左规模则表示其他人所印刷书籍量,这样左规模的最短时间即是B(左规模数量,k-1)了,至于右规模的最短时间,用相应B(右规模数量,1)-B(左规模数量,1)即可,把当前规模的右规模从l到k(如果有k个人印k本书,一人一本肯定最短时间,因此预留k本书)的所有最短时间取最小值,即当前规模最小时间。那么,只需要提供k-1人的1到l数据规模的最短时间即可递推B(l,k)。

思路实现代码:

int Method(int *n,int len,int k){ if(k>len) k=len; int **matrix=new int *[len]; for(int i=0;i<len;++i) matrix[i]=new int[k+1], ZeroMemory(matrix[i],k*4+4); int res=0; matrix[0][1]=n[0]; for(int i=1;i<len;++i) matrix[i][1]=matrix[i-1][1]+n[i]; for(int i=2;i<=k;++i) for(int p=i-1;p<len;++p) for(int t=i-1;t<=p;++t) { res=max(matrix[t-1][i-1], matrix[p][1]-matrix[t-1][1]); matrix[p][i]=matrix[p][i]==0?res:min(matrix[p][i],res); } res=matrix[len-1][k]; for(int i=0;i<len;++i) delete[] matrix[i]; delete[] matrix; return res;}
上一篇:Sticks --dfs 剪枝

下一篇:简单了解一下xml

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表