筆記：【演算法新手村】[初階]筆記03 - 二分練習題

題目

木材廠有 n 根原木，現在想把這些木頭切割成 k 段長度均為 l 的小段木頭（木頭有可能有剩餘）。
當然，我們希望得到的小段木頭越長越好，請求出 l 的最大值。
木頭長度的單位是 cm，原木的長度都是正整數，我們要求切割得到的小段木頭的長度也是正整數。
例如有兩根原木長度分別為 11 和 21，要求切割成等長的 6 段，很明顯能切割出來的小段木頭長度最長為 5。

• 輸入格式
  第一行是兩個正整數 n,k，分別表示原木的數量，需要得到的小段的數量。
  接下來 n 行，每行一個正整數 Lᵢ，表示一根原木的長度。

• 輸出格式
  僅一行，即 l 的最大值。
  如果連 1cm 長的小段都切不出來，輸出 0。

限制條件：

註：小段的木頭不能跟小段的木頭拼成一個大木頭(不能用 2 個 2cm 的木頭拼成 4cm 的木頭)

解題思路

雖然大家看到連到二分的筆記去就知道用二分了，但我這邊按照慣例還是解釋一下：簡單來說，因為題目要求的是可切成的最長長度，當一個長度可以時，小於那個長度的都可以不用管他，所以我們只需要去看更長的長度可不可以就好，所以可以二分答案。

(以下的l皆為二分搜尋用的，不是題目中的)
我們來想一下邊界條件，l 是最少的木頭長度(Lᵢ最小值 1 )，r是最多的木頭長度(Lᵢ最大值 10⁸ )，這樣就可以了，當然你會發現我的程式中是對輸入高度取最大值，兩個都可以，你只需要確保你的答案一定是介於l跟r之間就好，接下來就是check()函數，我要檢查當前長度有沒有辦法達成最少段數，直接用整除即可。

要特別注意幾點：

1. ans 要初始化為0，當長度太長時 check() 永遠都是false，因為題目有提到

如果連 1cm 長的小段都切不出來，輸出 0。

2. if(total >= k) return true; 可以省去很多不必要的運算，例如我n = 10000，可是我加兩次就已經滿足了，這時後面的全都是白費工夫，所以我們可以提前跳出。

程式碼實作 (C++)

#include <iostream>
#include <climits>

using namespace std;

bool check(int *arr , int n , int x , int k){
    if(x == 0) return false;
    long long total = 0;
    for(int i = 0 ; i  < n ; i++){
        total += arr[i]/x;
        if(total >= k) return true;
    }
    return total >= k;
}

int main(){

    int n , k;
    cin >> n >> k;
    int arr[(int)1e5+10];
    int Max = INT_MIN;
    for(int i = 0 ; i < n ; i++){
        cin >> arr[i];
        Max = max(Max,arr[i]);
    }

    int l = 0 , r = Max;
    int mid;
    int ans = 0;

    while (l <= r)
    {
        mid = (l+r)/2;
        if(check(arr,n,mid,k)){
            ans = mid;
            l = mid+1;
        }
        else{
            r = mid - 1;
        }
    }
    
    cout << ans;
    

    return 0;
}