成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode] Wood Cut

chanthuang / 1703人閱讀

摘要：有長(zhǎng)度為的一堆木頭，要切出段相同長(zhǎng)度的木頭，找到最大可能切出的長(zhǎng)度?？紤]兩種極端的長(zhǎng)度，單位，以及后最長(zhǎng)那根木頭的長(zhǎng)度，。若小于要求的，就必須減小。最后和相交時(shí)的，就是所求的最大長(zhǎng)度。

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

有長(zhǎng)度為L(zhǎng)[]的一堆木頭，要切出k段相同長(zhǎng)度的木頭，找到最大可能切出的長(zhǎng)度。
考慮兩種極端的長(zhǎng)度，單位1，以及sort后最長(zhǎng)那根木頭的長(zhǎng)度，L[n-1]。我們要找的答案一定在這兩種長(zhǎng)度之間，所以可以用二分法。
在1和L[n-1]作為start和end的情況下，我們需要計(jì)算每個(gè)對(duì)應(yīng)的mid，以及這個(gè)mid所對(duì)應(yīng)的能切成的等長(zhǎng)木段數(shù)sum。若sum大于要求的k，那么還可以增大mid的長(zhǎng)度，也就是令start前移到mid，繼續(xù)計(jì)算。若sum小于要求的k，就必須減小mid。最后start和end相交時(shí)的mid，就是所求的最大長(zhǎng)度。

不過(guò)在這個(gè)二分法的使用中，我們?cè)谧詈筇鰓hile循環(huán)之后很難分別判斷start和end哪個(gè)能夠滿足條件。因?yàn)楸仨氈匦掠胹tart，end甚至start + 1，end - 1計(jì)算sum，才能得到最優(yōu)的結(jié)果。所以，我們要令start和end最終相交于一點(diǎn)，同時(shí)直接得到所求最優(yōu)解，直到下一次循環(huán)`start > end`時(shí)，結(jié)束循環(huán)。

**這種循環(huán)的寫(xiě)法是：**

**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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65653.html

相關(guān)文章

  • [LintCode] Palindrome Partitioning II

    摘要：假設(shè)我們從后向前，分析到第位，開(kāi)始判斷，若為，說(shuō)明從第位向前到第位的子串是一個(gè)回文串，則就等于第位的結(jié)果加。然后讓繼續(xù)增大，判斷第位到最后一位的范圍內(nèi)，有沒(méi)有更長(zhǎng)的回文串，更長(zhǎng)的回文串意味著存在更小的，用新的來(lái)替換。 Problem Given a string s, cut s into some substrings such that every substring is a p...

    funnyZhang 評(píng)論0 收藏0

  • 大數(shù)據(jù)和云計(jì)算是天作之合

    摘要：首席數(shù)據(jù)科學(xué)家亞馬遜云計(jì)算首席數(shù)據(jù)科學(xué)家認(rèn)為，大數(shù)據(jù)和云計(jì)算是天作之合，云計(jì)算平臺(tái)的海量低成本的數(shù)據(jù)存儲(chǔ)與處理資源為大數(shù)據(jù)分享提供了可能。大數(shù)據(jù)尤其是和云計(jì)算年紀(jì)相仿，相輔相成，可謂天作之合。 　???????????????????????????????????????...

    Simon_Zhou 評(píng)論0 收藏0

  • JavaScript構(gòu)造器理解

    摘要：類類的概念應(yīng)該是面向?qū)ο笳Z(yǔ)言的一個(gè)特色，但是并不像，等高級(jí)語(yǔ)言那樣擁有正式的類，而是多數(shù)通過(guò)構(gòu)造器以及原型方式來(lái)仿造實(shí)現(xiàn)。因此，出現(xiàn)了構(gòu)造函數(shù)方式，它的關(guān)鍵在于構(gòu)造器概念的引入。于是，這就產(chǎn)生了構(gòu)造函數(shù)原型法的類構(gòu)造方法。 類 Class 類的概念應(yīng)該是面向?qū)ο笳Z(yǔ)言的一個(gè)特色，但是JavaScript并不像Java，C++等高級(jí)語(yǔ)言那樣擁有正式的類，而是多數(shù)通過(guò)構(gòu)造器以及原型方式...

    PiscesYE 評(píng)論0 收藏0

  • 比原鏈設(shè)計(jì)思考: 擴(kuò)展性UTXO模型

    摘要：的起源來(lái)自高明的中本聰中本聰對(duì)比特幣的設(shè)計(jì)，讓整個(gè)世界進(jìn)入了數(shù)字貨幣時(shí)代。比原鏈的思考馬克思哲學(xué)的否定之否定規(guī)律，事物的發(fā)展變化是螺旋式上升的。 用戶模型是比原鏈在最初就需要確定的重要數(shù)據(jù)結(jié)構(gòu)， 團(tuán)隊(duì)的選擇還是聚焦在兩種典型的模型系統(tǒng)中，Account模型和UTXO模型，和其他大多數(shù)區(qū)塊鏈設(shè)計(jì)一樣， 選擇了模型就決定了協(xié)議層的重要實(shí)現(xiàn)，兩種模型各有利弊，不同區(qū)塊鏈針對(duì)想聚焦的場(chǎng)景自身會(huì)...

    Vicky 評(píng)論0 收藏0

  • 劍指offer/LintCode12_最小棧

    摘要：劍指最小棧聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處解題思路實(shí)現(xiàn)功能實(shí)現(xiàn)一個(gè)最小棧，要求操作均為復(fù)雜度，解題思路用棧存儲(chǔ)數(shù)據(jù)用最小棧存儲(chǔ)中最小元素，保證棧頂元素與棧頂元素同步，表示此時(shí)最小值將與此時(shí)最小值比較，將更小的一方壓棧，保證中棧頂始終 劍指offer/LintCode12_最小棧 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處https://segmentfault.com/u/yz...

    Betta 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<