S*******C
发帖数: 822 | 1 Wood Cut
18%
Accepted
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.
Note
You couldn't cut wood into float length.
Example
For L=[232, 124, 456], k=7, return 114.
Challenge
O(n log Len), where Len is the longest length of the wood.
http://lintcode.com/en/problem/wood-cut/
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) {
// write your code here
}
} | j********g
发帖数: 80 | | c********w
发帖数: 2438 | 3 po个我的
public int woodCut(int[] L, int k) {
// write your code here
int n=L.length;
if(n==0)
return 0;
Arrays.sort(L);
int res=0;
int left=1, right=L[n-1];
while(left<=right){
int mid=(right-left)/2+left;
int count=0;
for(int i=n-1;i>=0;i--)
count+=(L[i]/mid);
if(count>=k){
res=mid;
left=mid+1;
}
else{
right=mid-1;
}
}
return res;
} | c****8
发帖数: 76 | 4 lintcode 跟 leetcode的区别是啥？这两个上面的题目差别很大么？要不要两个都刷下
？ | d****n
发帖数: 397 | 5 这个简单，二分查找。［0， max（L）］区间开始，然后一直找下去，到区间长度为一。
small
【在 S*******C 的大作中提到】
: Wood Cut
: 18%
: Accepted
: 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.
: Note
: You couldn't cut wood into float length.
: Example
|
|
