題目如下： 給出一個數(shù)組A包含n個元素，表示n本書以及各自的頁數(shù)。現(xiàn)在有個k個人復(fù)印書籍，每個人只能復(fù)印連續(xù)一段編號的書，比如A[1],A[2]由第一個人復(fù)印，但是不能A[1],A[3]由第一個人復(fù)印，求最少需要的時間復(fù)印所有書。
樣例： A = [3,2,4],k = 2
返回5，第一個人復(fù)印前兩本書
解題思路： 這個題有一定難度，先提出合理假設(shè)B（l，k）為l個數(shù)據(jù)規(guī)模的k人分配使用最短時間。把數(shù)據(jù)規(guī)模劃分為兩部分，從右到左，依次增加右規(guī)模，表示第k人印刷書籍量，而左規(guī)模則表示其他人所印刷書籍量，這樣左規(guī)模的最短時間即是B（左規(guī)模數(shù)量，k-1）了，至于右規(guī)模的最短時間，用相應(yīng)B（右規(guī)模數(shù)量，1）-B（左規(guī)模數(shù)量，1）即可，把當(dāng)前規(guī)模的右規(guī)模從l到k（如果有k個人印k本書，一人一本肯定最短時間，因此預(yù)留k本書）的所有最短時間取最小值，即當(dāng)前規(guī)模最小時間。那么，只需要提供k-1人的1到l數(shù)據(jù)規(guī)模的最短時間即可遞推B（l，k）。
思路實現(xiàn)代碼：
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;}新聞熱點
疑難解答
