# 183.Wood Cut

## 1.Description(Hard)

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.

### Notice

You couldn't cut wood into float length.

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

**Example**

For`L=[232, 124, 456]`,`k=7`, return`114`.

[**Challenge**](https://www.lintcode.com/en/problem/wood-cut/#challenge)

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

[**Tags**](https://www.lintcode.com/en/problem/wood-cut/#tags)

[Binary Search](https://www.lintcode.com/tag/binary-search/)

## 2.Code

用一个count函数计算当前长度能切成多少块，用binary search来缩小范围。

```
public int woodCut(int[] L, int k) {
        int maxwood=0;
        for(int i=0;i<L.length;i++){
            maxwood=Math.max(maxwood, L[i]);
        }

        int start=1,end=maxwood;
        while(start+1<end){
            int mid=start+(end-start)/2;
            if(count(L,mid)==k){
                start=mid;
            }
            else if(count(L,mid)>k){
                start=mid;
            }
            else{
                end=mid;
            }
        }
        // find the largest length that can cut more than k pieces of wood
        if(count(L,end)>=k){
            return end;
        }
        if(count(L,start)>=k){
            return start;
        }
        return 0;       
    }

    public int count(int[] L, int len){
        int count=0;
        for(int i=0;i<L.length;i++){
            count+=L[i]/len;
        }
        return count;
    }
```
