Wood Cut

Wood Cut.png

===================== 解題思路 =====================

關鍵是找到 binary search 的 right bound ( 最大可能的解 ), 題目告知可以從 vector 裡的最大值著手 所以掃一遍 vector 找到最大值即可用基本 BS 方式解決

===================== C++ code ====================

<pre><code>
class Solution {

public:

/** 
 *@param L: Given n pieces of wood with length L[i]
 *@param k: An integer
 *return: The maximum length of the small pieces.
 */
bool isValid(vector<int> &L, int mid, int k)
{
    int sum = 0;
    for(int i = 0; i < L.size(); i++)
    {
        sum += L[i] / mid;
    }
    return sum >= k;
}

int woodCut(vector<int> L, int k) {
    // write your code here
    long left = 0, right = 0;
    //get the right bound
    for(int i = 0; i < L.size(); i++)
    {
        if(L[i] > right) right = L[i];
    }
    //binary search
    while(left + 1 < right)
    {
        long mid = left + (right - left) / 2;
        if(isValid(L, mid, k)) left = mid;
        else right = mid;
    }
    if(isValid(L, right, k)) return right;
    else return left;
}

};
<code><pre>