木材加工

有一些原木，現在想把這些木頭切割成一些長度相同的小段木頭，需要得到的小段的數目至少為?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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。