【題目描述】
Given n pieces of wood with lengthL[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.
有一些原木泽篮，現(xiàn)在想把這些木頭切割成一些長(zhǎng)度相同的小段木頭互广，需要得到的小段的數(shù)目至少為k魏烫。當(dāng)然，我們希望得到的小段越長(zhǎng)越好厌杜，你需要計(jì)算能夠得到的小段木頭的最大長(zhǎng)度。
【注】：木頭長(zhǎng)度的單位是厘米。原木的長(zhǎng)度都是正整數(shù)侯嘀，我們要求切割得到的小段木頭的長(zhǎng)度也要求是整數(shù)日戈。無(wú)法切出要求至少k段的,則返回0即可询张。
【題目鏈接】
www.lintcode.com/en/problem/wood-cut/
【題目解析】
這道題要直接想到二分搜素其實(shí)不容易，但是看到題中 Challenge 的提示后你大概就能想到往二分搜索上靠了浙炼。
首先來(lái)分析下題意份氧，題目意思是說(shuō)給出 n 段木材L[i], 將這 n 段木材切分為至少 k 段，這 k 段等長(zhǎng)鼓拧，求能從 n 段原材料中獲得的最長(zhǎng)單段木材長(zhǎng)度半火。以 k=7 為例，要將 L 中的原材料分為7段季俩，能得到的最大單段長(zhǎng)度為114, 232/114 = 2, 124/114 = 1, 456/114 = 4, 2 + 1 + 4 = 7.
理清題意后我們就來(lái)想想如何用算法的形式表示出來(lái)钮糖，顯然在計(jì)算如2,1,4等分片數(shù)時(shí)我們進(jìn)行了取整運(yùn)算，在計(jì)算機(jī)中則可以使用下式表示： ∑?i=1?n???l??L[i]??≥k
其中 l 為單段最大長(zhǎng)度酌住，顯然有 1≤l≤max(L[i]). 單段長(zhǎng)度最小為1店归，最大不可能超過(guò)給定原材料中的最大木材長(zhǎng)度。
【參考答案】
