text: ### 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)
  ``````
metadata: {"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}