### 183.Wood Cut

Given n pieces of wood with length`L[i]`(integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. 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`.

### Challenge

O(n log Len), where Len is the longest length of the wood.

### Notice

You couldn't cut wood into float length.

If you couldn't get >=_k _pieces, return`0`.

Thoughts:

1. Binary Search on the length by testing the resulted cutting pieces

Code: T: Nlog(max(L[i])), S: O(1)

``````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) {

int l = 1, r = 0;
for (int len : L){
r = Math.max(r, len);

}
if(k == 0) return r;

while (l <= r){
int mid = l + ((r - l) >> 1);
if (count(L, mid) >= k) l = mid + 1;
else r = mid - 1;
}

// if (count(L,l) >= k) return l;
if (count(L,r) >= k) return r;

return 0;

}

private int count(int[] L, int query){
int sum = 0;
if (query == 0) return 0; // in case of dividing with 0
for (int len : L){
sum+= len/query;
}
return sum;
}
}
``````
``````出来之后看的标准的做法是用二分法加greedy去找, N * log max

dp[i][j] = 把前0 - i 根木头切 j段的最大长度 j < k

dp[i][j] = max(min(dp[i - 1][a], wood[i] / (j - a)) for a < j)
``````
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}