[LintCode] Wood Cut

chanthuang 发布于2019-08-14 15:20 / 1700人阅读

摘要：有长度为的一堆木头，要切出段相同长度的木头，找到最大可能切出的长度。考虑两种极端的长度，单位，以及后最长那根木头的长度，。若小于要求的，就必须减小。最后和相交时的，就是所求的最大长度。

Problem

Given n pieces of wood with length L[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.

Notice

You couldn"t cut wood into float length.

Example

For L=[232, 124, 456], k=7, return 114.

Challenge

O(n log Len), where Len is the longest length of the wood.

Note

有长度为L[]的一堆木头，要切出k段相同长度的木头，找到最大可能切出的长度。
考虑两种极端的长度，单位1，以及sort后最长那根木头的长度，L[n-1]。我们要找的答案一定在这两种长度之间，所以可以用二分法。
在1和L[n-1]作为start和end的情况下，我们需要计算每个对应的mid，以及这个mid所对应的能切成的等长木段数sum。若sum大于要求的k，那么还可以增大mid的长度，也就是令start前移到mid，继续计算。若sum小于要求的k，就必须减小mid。最后start和end相交时的mid，就是所求的最大长度。

不过在这个二分法的使用中，我们在最后跳出while循环之后很难分别判断start和end哪个能够满足条件。因为必须重新用start，end甚至start + 1，end - 1计算sum，才能得到最优的结果。所以，我们要令start和end最终相交于一点，同时直接得到所求最优解，直到下一次循环`start > end`时，结束循环。

**这种循环的写法是：**

**1.** 
`while (start <= end)`
**2.**
 if (mid satisfies or about to satisfy the requirement) {
       res = mid;
       start = mid++;
       }
**3.**
 else end = mid--;

Solution

public class Solution {
    public int woodCut(int[] L, int k) {
        int n = L.length;
        if (n == 0) return 0;
        Arrays.sort(L);
        int start = 1;
        int end = L[n-1];
        int res = 0;
        while (start <= end) {
            int mid = start + (end - start)/2;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum+=L[i]/mid;
            }
            if (sum >= k) {
                res = mid;
                start = mid + 1;
            }
            else end = mid - 1;
        }
        return res;
    }
}

GPU云服务器云服务器 Wood LintCode cut LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65653.html

[LintCode] Palindrome Partitioning II

摘要：假设我们从后向前，分析到第位，开始判断，若为，说明从第位向前到第位的子串是一个回文串，则就等于第位的结果加。然后让继续增大，判断第位到最后一位的范围内，有没有更长的回文串，更长的回文串意味着存在更小的，用新的来替换。 Problem Given a string s, cut s into some substrings such that every substring is a p...

funnyZhang 2019-08-14 15:30 评论0 收藏0
大数据和云计算是天作之合

摘要：首席数据科学家亚马逊云计算首席数据科学家认为，大数据和云计算是天作之合，云计算平台的海量低成本的数据存储与处理资源为大数据分享提供了可能。大数据尤其是和云计算年纪相仿，相辅相成，可谓天作之合。　 ...

Simon_Zhou 2019-04-25 17:33 评论0 收藏0
JavaScript构造器理解

摘要：类类的概念应该是面向对象语言的一个特色，但是并不像，等高级语言那样拥有正式的类，而是多数通过构造器以及原型方式来仿造实现。因此，出现了构造函数方式，它的关键在于构造器概念的引入。于是，这就产生了构造函数原型法的类构造方法。类 Class 类的概念应该是面向对象语言的一个特色，但是JavaScript并不像Java，C++等高级语言那样拥有正式的类，而是多数通过构造器以及原型方式...

PiscesYE 2019-08-21 10:30 评论0 收藏0
比原链设计思考: 扩展性UTXO模型

摘要：的起源来自高明的中本聪中本聪对比特币的设计，让整个世界进入了数字货币时代。比原链的思考马克思哲学的否定之否定规律，事物的发展变化是螺旋式上升的。用户模型是比原链在最初就需要确定的重要数据结构，团队的选择还是聚焦在两种典型的模型系统中，Account模型和UTXO模型，和其他大多数区块链设计一样，选择了模型就决定了协议层的重要实现，两种模型各有利弊，不同区块链针对想聚焦的场景自身会...

Vicky 2019-06-27 18:33 评论0 收藏0
剑指offer/LintCode12_最小栈

摘要：剑指最小栈声明文章均为本人技术笔记，转载请注明出处解题思路实现功能实现一个最小栈，要求操作均为复杂度，解题思路用栈存储数据用最小栈存储中最小元素，保证栈顶元素与栈顶元素同步，表示此时最小值将与此时最小值比较，将更小的一方压栈，保证中栈顶始终剑指offer/LintCode12_最小栈声明文章均为本人技术笔记，转载请注明出处https://segmentfault.com/u/yz...

Betta 2019-08-14 18:12 评论0 收藏0