木頭加工

題目描述

有一些原木，現在想把這些木頭切割成一些長度相同的小段木頭，需要得到的小段的數目至少為?k。當然，我們希望得到的小段越長越好，你需要計算能夠得到的小段木頭的最大長度。

注意事項

木頭長度的單位是厘米。原木的長度都是正整數，我們要求切割得到的小段木頭的長度也要求是整數。無法切出要求至少?k?段的,則返回?0?即可。

樣例

有3根木頭[232, 124, 456],?k=7, 最大長度為114,則返回114。

簡單分析

暴力解法就是從1開始遍歷所有的長度，對于長度L，計算所有木頭可以切多少段，如果滿足要求就記錄長度并繼續增加，如果不滿足則終止循環，并返回記錄的長度L。

暴力解法的復雜度是O(n*m)其中n是木頭數組的長度，m指的是數組中數據最大值，因為對于每一個長度都需要遍歷整個數組，而最后的數組大小基本正比于數組中的最大值。

在暴力解法的基礎上，我們可以改進為O(n*log m)復雜度的算法，先找到最長的木頭長度maxl（數組中的最大值），然后利用二分法搜索0-maxl之間的值，最后輸出滿足要求的最大值。

程序

public int woodCut(int[] L, int k) {int l = L.length;if(l == 0) return 0; //如果輸入數組L為空則直接返回0int maxL = L[0]; //找到數組中的最大值for(int i = 1; i < l; i++){int temp = L[i];if(temp > maxL){maxL = temp;}}int up = maxL;int down = 0;int res = 0;while(up >= down){ //二分法查找int len = down + (up - down)/2;if(len == 0) return 0;int c = count(L,len);if(c >= k) {res = res>=len?res:len;down = len + 1;} //符號是>=else if(c < k) up = len - 1;}return res;}public int count(int[] L,int length){int num = 0;for(int l:L){num += l/length;}return num;} }

上面的算法運行速度仍然很慢，在lintcode網站提交以后運行時間是3s以上，很慢。大家可以試著優化一下。

ps：提供一個教訓，我是想法是，當最后分割的長度正好是k段時，我再更新最終的結果長度res。也就是把二分搜索部分修改如下

while(up >= down){int len = down + (up - down)/2;if(len == 0) return 0;int c = count(L,len);if(c < k) up = len - 1;else{ if(c == k) res = res>=len?res:len; down = len + 1;}}

首先，上面這個程序是錯誤的。如果最大值對應的段數不是k的話，那我們的程序就無法輸出正確結果。這是我個人嘗試中的一點經驗。

一些閑話：

博客這邊更新的題目都是略帶難度的，還有一些只需要簡單技巧的題目就不在這里寫了，盡量寫在github上了。一個不算項目的小項目,現在內容還比較少，大家喜歡可以支持一下。

轉載于:https://www.cnblogs.com/GuoYaxiang/p/6127404.html

總結

以上是生活随笔為你收集整理的【刷题笔记】--lintcode木头加工（java）的全部內容，希望文章能夠幫你解決所遇到的問題。

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