Wood Cut

Love The Way You Lie 2021-12-17 10:27 144阅读 0赞

http://www.lintcode.com/zh-cn/problem/wood-cut/

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

#####  注意事项 #####

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

Lintcode上面的一道题目，很有意思，光看题可能想象不出是用二分来做。但是实际小段的长度可以使用二分来确定。left为0，right为原始木头的最长长度（注意不是最小长度）。但是这道题二分的复杂度也不是O(logn)而是和木头的数目也成正比关系（每次对于划分的长度，需要计算一遍所有的木头得到可以锯出的小段数目）。具体代码如下：

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.
        """
        def woodCut(self, L, k):
            if not L:
                return 0
    
            l = 0
            r = max(L)
            
            while l+1 < r:
               mid = l + (r-l)/2
               if  sum([i/mid  for i in L]) >= k:
                   l = mid 
               else:
                   r = mid
            if sum([i/r for i in L]) < k:
                return l 
            else:
                return r

转载于:https://www.cnblogs.com/sherylwang/p/5496459.html

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关 cut 命令

参考：https://linux.cn/article-9895-1.html][https_linux.cn_article-9895-1.html] 转载于:htt...

痛定思痛。/ 2024年04月20日 10:19/ 0 赞/ 23 阅读

相关 Cutting Bamboos

可持久线段树 [https://ac.nowcoder.com/acm/problem/52172][https_ac.nowcoder.com_acm_problem_52

小灰灰/ 2023年08月17日 16:26/ 0 赞/ 68 阅读

相关 cut命令详解

cut是一个选取命令，就是将一段数据经过分析，取出我们想要的。一般来说，选取信息通常是针对“行”来进行分析的，并不是整篇信息分析的。 (1)其语法格式为： cut \[-

分手后的思念是犯贱/ 2022年11月22日 00:02/ 0 赞/ 132 阅读

相关 cut命令使用

cut -b list [-n] [file ...] cut -c list [file ...] cut -f list [-d

た入场券/ 2022年09月12日 09:53/ 0 赞/ 125 阅读

相关 linux - grep | cut

grep命令： ![Center][] 下面是cut命令： ![Center 1][] ![Center 2][] [Center]: /images/

骑猪看日落/ 2022年07月24日 12:21/ 0 赞/ 145 阅读

相关 cut

1 一两句话描述一下cut命令吧! 正如其名，cut的工作就是“剪”，具体的说就是在文件中负责剪切数据用的。 cut是以每一行为一个处理对象的，这种机制和sed是一样的

痛定思痛。/ 2022年06月14日 05:58/ 0 赞/ 120 阅读

相关《Norwegain Wood》—— The Beatles

I once had a girl 我曾经拥有过一个女孩 Or should I say, she once had me? 或是说，她曾经拥有我 She showed

忘是亡心i/ 2022年04月23日 09:44/ 0 赞/ 64 阅读

相关 Wood Cut

http://www.lintcode.com/zh-cn/problem/wood-cut/ 有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目

Love The Way You Lie/ 2021年12月17日 10:27/ 0 赞/ 145 阅读

相关 linux cut 命令

cut: 作用：和名字一样，就是“剪”掉一些东西，析取我们所要的东西 cut命令主要是接受三个定位方法：第一，字节（bytes），用选项-b 第二，字符（chara

本是古典何须时尚/ 2021年06月24日 13:58/ 0 赞/ 381 阅读

相关 Linux cut命令

Linux cut命令用于显示每行从开头算起 num1 到 num2 的文字。参数: - -b ：以字节为单位进行分割。这些字节位置将忽略多字节字符边界，除非也指定了 -...

灰太狼/ 2020年05月25日 15:48/ 0 赞/ 686 阅读