[LintCode] Wood Cut

chanthuang 發布于2019-08-14 15:20 / 1699人閱讀

摘要：有長度為的一堆木頭，要切出段相同長度的木頭，找到最大可能切出的長度。考慮兩種極端的長度，單位，以及后最長那根木頭的長度，。若小于要求的，就必須減小。最后和相交時的，就是所求的最大長度。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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