有n本書和k個抄寫員。要求n本書必須連續(xù)地分配給這k個抄寫員抄寫。也就是說前a1本書分給第一個抄寫員，接下來a2本書分給第二個抄寫員，如此類推（a1,a2需要你的算法來決定）。給定n,k和每本書的頁數(shù)p1,p2..pn，假定每個抄寫員速度一樣（每分鐘1頁），k個抄寫員同時開始抄寫，問最少需要多少時間能夠?qū)⑺袝砍瓕懲旯?#xff1f;

樣例

Given array A =?[3,2,4], k =?2.

Return?5( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )

解答?

解法1：動態(tài)規(guī)劃

設(shè)f[i][j]代表前i本書分給j個抄寫員抄完的最少耗時。答案就是f[n][k]。狀態(tài)轉(zhuǎn)移方程f[i][j] = min{max(f[x][j-1], sum(x+1, i)), j<x<i}。其中x是在枚舉第j個抄寫員是從哪本書開始抄寫。

時間復(fù)雜度O(n^2*k)

解法2；動態(tài)規(guī)劃+決策單調(diào)。

同上一解法，但在x的枚舉上進(jìn)行優(yōu)化，設(shè)s[i][j]為使得f[i][j]獲得最優(yōu)值的x是多少。有s[i][j+1]>=s[i][j]>=s[i-1][j]。因此x這一層的枚舉不再是每次都是n而是總共加起來n。

時間復(fù)雜度O(n*k)

解法3：二分答案

二分答案，然后嘗試一本本的加進(jìn)來，加滿了就給一個抄寫員。看最后需要的抄寫員數(shù)目是多余k個還是少于k個，然后來決定是將答案往上調(diào)整還是往下調(diào)整。其實可以這樣想：如果一個人抄書那么耗時 maxTime , which is the sum of all pages （上限）.
?如果有足夠多人，則最小耗時為所有書中最大值 (下限)
答案必然在minTime and maxTime 之間, 用?二分法找出滿足條件的答案

時間復(fù)雜度O( n log Sum(pi) )

// http://www.jiuzhang.com/problem/2/ class Solution { public:/*** @param pages: a vector of integers* @param k: an integer* @return: an integer*/// 解法1： 動態(tài)規(guī)劃// 設(shè)f[i][j]代表前i本書分給j個抄寫員抄完的最少耗時。答案就是f[n][k]。// 思考最后一個人需要抄幾本書// 狀態(tài)轉(zhuǎn)移方程f[i][j] = min{max(f[x][j-1], sum(x+1, i)), j<x<i}。其中x是在枚舉第j個抄寫員是從哪本書開始抄寫。// 時間復(fù)雜度O(n^2*k)int copyBooks1(vector<int> &pages, int k) {// write your code hereint n = pages.size(); // book numberif(n == 0){return 0;}int ans = 0;//預(yù)處理邊界條件if(k > n){for(int i = 0; i < n; i++){ans = max(ans, pages[i]);}return ans;}//f[i][j] 表示前i本書分給j給人抄的最少花費時間vector<vector<int> > f(n+1, vector<int>(k+1, 0));int maxPage = 0;for(int i = 0; i < n; i++){maxPage = max(maxPage, pages[i]);}for(int i = 1; i <= n; i++){f[i][0] = numeric_limits<int>::max();}// prepare sum startvector<int> sum(n, 0);// sum[i] 表示從pages[0]到pages[i]的前綴和sum[0] = pages[0];for(int i = 1; i < n; i++){sum[i] = pages[i] + sum[i-1];}// prepare sum endfor(int i = 1; i <= n; i++){for(int j = 1; j <= k; j++){int minTime = numeric_limits<int>::max();for(int x = j-1; x < i; x++) { // 枚舉最后一個人從哪本書開始抄// x表示前面j-1 個人抄x本書(至少j-1本，否則不夠抄),// 最后一個人抄第x+1本(下標(biāo)x)到最后第i本(下標(biāo)i-1)minTime = min(minTime,max(f[x][j-1], sum[i-1] - sum[x-1]));}f[i][j] = minTime;}}return f[n][k];}// 解法2： 二分法// 二分答案，然后嘗試一本本的加進(jìn)來，加滿了就給一個抄寫員。// 看最后需要的抄寫員數(shù)目是多余k個還是少于k個，然后來決定是將答案往上調(diào)整還是往下調(diào)整。// 時間復(fù)雜度O( n log Sum(pi) )int copyBooks(vector<int> &pages, int k) {int n = pages.size(); // book numberif(n == 0){return 0;}int ans = 0;//預(yù)處理邊界條件if(k > n){for(int i = 0; i < n; i++){ans = max(ans, pages[i]);}return ans;}int minTime = numeric_limits<int>::min();int maxTime = 0;for(int i = 0; i < n; i++){minTime = max(minTime, pages[i]); // min of booksmaxTime += pages[i];// sum of all}//可以這樣想：如果一個人抄書那么耗時 maxTime , which is the sum of all pages （上限）.// 如果有足夠多人，則最小耗時為所有書中最大值 (下限)//答案必然在minTime and maxTime 之間// 二分法找出滿足條件的答案int start = minTime, end = maxTime;while(start < end){int mid = start + (end - start) / 2;if(search(mid, pages, k)){// 此時已經(jīng)滿足條件n本書由k個人抄完，但是我們要找最小費時，所以繼續(xù)往左邊區(qū)間找// 由于mid 是可能的答案之一，所以不能mid-1.end = mid;}else {// 在mid時間內(nèi)無法抄完start = mid + 1;}}return start;}// search 函數(shù)返回值表示k個人在target 時間能否抄完所有書bool search(int target, vector<int> &pages, int k){int count = 1; // how many people neededint sum = 0;int i = 0;while(i < pages.size()){if(sum + pages[i] <= target){ // 每個人在target時間內(nèi)盡量多抄sum += pages[i++];}else if(pages[i] <= target){count++;//上一個人抄不完，由另外一個人抄sum = pages[i++];}else {// 單本書就已經(jīng)超時了，直接returnreturn false;}}return count <= k;} };

總結(jié)

以上是生活随笔為你收集整理的抄书问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。