Lintcode183 Wood Cut solution 题解
发布在lintcode2018年1月21日view:191
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

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.

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

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

【题目链接】

www.lintcode.com/en/problem/wood-cut/

【题目解析】

这道题要直接想到二分搜素其实不容易,但是看到题中 Challenge 的提示后你大概就能想到往二分搜索上靠了。

首先来分析下题意,题目意思是说给出 n 段木材L[i], 将这 n 段木材切分为至少 k 段,这 k 段等长,求能从 n 段原材料中获得的最长单段木材长度。以 k=7 为例,要将 L 中的原材料分为7段,能得到的最大单段长度为114, 232/114 = 2, 124/114 = 1, 456/114 = 4, 2 + 1 + 4 = 7.

理清题意后我们就来想想如何用算法的形式表示出来,显然在计算如2,1,4等分片数时我们进行了取整运算,在计算机中则可以使用下式表示: ∑​i=1​n​​​l​​L[i]​​≥k

其中 l 为单段最大长度,显然有 1≤l≤max(L[i]). 单段长度最小为1,最大不可能超过给定原材料中的最大木材长度。

【参考答案】

www.jiuzhang.com/solutions/wood-cut/

作者:程风破浪会有时 链接:https://www.jianshu.com/p/7c08d08ca0b6 來源:简书 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
lintcode

lintcode题解

我的收藏