# Wood Cut ### Source - lintcode: [(183) Wood Cut](http://www.lintcode.com/en/problem/wood-cut/) ### Problem Given n pieces of wood with length `L[i]` (integer array). Cut them into smallpieces to guarantee you could have equal or more than k pieces with the samelength. What is the longest length you can get from the n pieces of wood?Given L & k, return the maximum length of the small pieces. #### Example For `L=[232, 124, 456]`, `k=7`, return `114`. #### Note You couldn't cut wood into float length. #### Challenge O(n log Len), where Len is the longest length of the wood. ### 題解 - 二分搜索 這道題要直接想到二分搜素其實不容易，但是看到題中 Challenge 的提示后你大概就能想到往二分搜索上靠了。首先來分析下題意，題目意思是說給出 n 段木材`L[i]`, 將這 n 段木材切分為至少 k 段，這 k 段等長，求能從 n 段原材料中獲得的最長單段木材長度。以 k=7 為例，要將 L 中的原材料分為7段，能得到的最大單段長度為114, 232/114 = 2, 124/114 = 1, 456/114 = 4, 2 + 1 + 4 = 7. 理清題意后我們就來想想如何用算法的形式表示出來，顯然在計算如`2`, `1`, `4`等分片數時我們進行了取整運算，在計算機中則可以使用下式表示：∑i=1nL[i]l≥k\sum _{i = 1} ^{n} \frac {L[i]}{l} \geq k∑i=1nlL[i]≥k 其中 lll 為單段最大長度，顯然有 1≤l≤max(L[i])1 \leq l \leq max(L[i])1≤l≤max(L[i]). 單段長度最小為1，最大不可能超過給定原材料中的最大木材長度。 ****> 注意求和與取整的順序，是先求 `L[i]/l`的單個值，而不是先對`L[i]`求和。 分析到這里就和題 [Sqrt x](http://algorithm.yuanbin.me/zh-cn/binary_search/sqrt_x.html) 差不多一樣了，要求的是 lll 的最大可能取值，同時 lll 可以看做是從有序序列`[1, max(L[i])]`的一個元素，典型的二分搜素！ P.S. 關于二分搜索總結在 [Binary Search](http://algorithm.yuanbin.me/zh-cn/basics_algorithm/binary_search.html) 一小節，直接套用『模板二——最優化』即可。 ### Python ~~~ class Solution: """ @param L: Given n pieces of wood with length L[i] @param k: An integer return: The maximum length of the small pieces. """ def woodCut(self, L, k): if sum(L) < k: return 0 max_len = max(L) start, end = 1, max_len while start + 1 < end: mid = start + (end - start) / 2 pieces_sum = sum([len_i / mid for len_i in L]) if pieces_sum < k: end = mid else: start = mid # corner case if end == 2 and sum([len_i / 2 for len_i in L]) >= k: return 2 return start ~~~ ### Java ~~~ public class Solution { /** *@param L: Given n pieces of wood with length L[i] *@param k: An integer *return: The maximum length of the small pieces. */ public int woodCut(int[] L, int k) { if (L == null || L.length == 0) return 0; int lb = 0, ub = Integer.MAX_VALUE; while (lb + 1 < ub) { int mid = lb + (ub - lb) / 2; if (C(L, k, mid)) { lb = mid; } else { ub = mid; } } return lb; } // whether it cut with length x and get more than k pieces private boolean C(int[] L, int k, int x) { int sum = 0; for (int l : L) { sum += l / x; } return sum >= k; } } ~~~ ### 源碼分析 定義私有方法`C`為切分為 x 長度時能否大于等于 k 段。若滿足條件則更新`lb`, 由于 lb 和 ub 的初始化技巧使得我們無需單獨對最后的 lb 和 ub 單獨求和判斷。九章算法網站上的方法初始化為1和某最大值，還需要單獨判斷，雖然不會出bug, 但稍顯復雜。這個時候lb, ub初始化為兩端不滿足條件的值的優雅之處就體現出來了。 ### 復雜度分析 遍歷求和時間復雜度為 O(n)O(n)O(n), 二分搜索時間復雜度為 O(logmax(L))O(\log max(L))O(logmax(L)). 故總的時間復雜度為 O(nlogmax(L))O(n \log max(L))O(nlogmax(L)). 空間復雜度 O(1)O(1)O(1). ### Reference - [Binary Search](http://algorithm.yuanbin.me/zh-cn/basics_algorithm/binary_search.html)