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