木材加工（LintCode）

木材加工

有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。

样例

有3根木头[232, 124, 456], k=7, 最大长度为114.

注意

木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可。

挑战

O(n log Len), Len为 n 段原木中最大的长度

 

要达到n*log Len ,可以想到的是用折半查找。需要注意的是不一定要将所有的木头都切了，过短的木头可以不切（一开始我认为所有的木头都需要切，或者说最后的长度不能超过最短的木头，于是拿到了一个WA）。第一次遍历数组，求和并求得最大值。若和小于k，则返回0.接下来在1—max之间用折半查找，找到最大的长度。

1 public class Solution { 2 /** 3 *@param L: Given n pieces of wood with length L[i] 4 *@param k: An integer 5 *return: The maximum length of the small pieces. 6 */ 7 public int woodCut(int[] L, int k) { 8 if (L.length == 0) { 9 return 0; 10 } 11 long sum = L[0]; 12 long max = L[0]; 13 14 for (int i=1;i<L.length;i++) { 15 sum += L[i]; 16 max = Math.max(L[i],max); 17 } 18 if (sum < k) { 19 return 0; 20 } 21 22 long i = 1; 23 long j = max; 24 25 while(i <= j) { 26 long mid = (i + j) / 2; 27 if (judge(L,k,mid)) { 28 i = mid + 1; 29 }else { 30 j = mid - 1; 31 } 32 } 33 34 return (int)j; 35 } 36 37 public boolean judge(int[] L,int k,long l){ 38 int num = 0; 39 for (int x : L) { 40 num += x/l; 41 } 42 if (num >= k) { 43 return true; 44 } 45 return false; 46 } 47 }

 

转载于:https://www.cnblogs.com/FJH1994/p/5041529.html

总结

以上是生活随笔为你收集整理的木材加工（LintCode）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。