183.Wood Cut

1.Description(Hard)

Given n pieces of wood with lengthL[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, return0.

Example

ForL=[232, 124, 456],k=7, return114.

Challenge

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

Tags

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;
    }