[leetcode/lintcode 題解] 百度面試真題：木材加工

描述

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

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

線上評測位址：

領扣題庫官網

樣例1
輸入:
L = [232, 124, 456]
k = 7
輸出: 114
Explanation: 我們可以把它分成114cm的7段，而115cm不可以           

樣例2
輸入:
L = [1, 2, 3]
k = 7
輸出: 0
說明:很顯然我們不能按照題目要求完成。           

算法：二分

題目意思是說給出n段木材L[i], 将這n段木材切分為至少k段，這k段等長，

若直接枚舉每段木材的長度則時間複雜度高達 O(n*maxL), 我們可以使用二分答案來優化枚舉木材長度的過程

• 設left=0,即木材長度最小為0，設right=max_L即所有木材中最長的長度，因為結果是不可能大于這個長度的，mid = left + right
• 若長度為mid時不能完成，說明太長了，那麼我們往區間[left,mid]搜，
• 若可以完成，說明也許可以更長，那麼我們往[mid,right]搜,
• 在check函數中，我們判斷用所有木頭除目前mid的值的和是否大于等于k，若小于則說明該mid不可行, 若大于等于則說明mid可行
• 由于判斷條件是left + 1 < right,最後結果就是left的值

複雜度分析

• 時間複雜度O(nlog（n）)
  • 二分查找的複雜度
• 空間複雜度O(size(L))
  • 隻有數組L

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) {
        int len_L = L.length;
        if (len_L == 0) {
            return 0;
        }
        int max_L = 0;//尋找最大值
        for (int i = 0;i < len_L;i++) {
            max_L = Math.max(max_L,L[i]);
        }
        long left = 0,right = max_L;
        int mid;
        while (left + 1 < right) {
            mid = (int)(left + (right - left) / 2);
            if (check(L, k, len_L, mid)) {//如果還能分更長的，則往[mid,right]走
                left = mid;
            }
            else {//如果不能分更長的，則往[left,mid]走
                right = mid;
            }
        }
        if(check(L,k,len_L,(int)right)) return (int)right;
        return (int)left;
    }
    private boolean check(int [] L,int k,int len_L,int mid){
        int count = 0;
        //計算目前長度下能分成幾段
        for (int i = 0;i < len_L;i++) {
            count += L[i] / mid;
        }
        //如果還能分更長的，傳回true
        if (count >= k) {
            return true;
        }
        //如果不能分更長的，傳回false
        return false;
    }
}           

更多題解參考： 九章官網solution