题目如下: 给出一个数组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;}新闻热点
疑难解答