Ch17 二分搜尋法

# Ch17 二分搜尋法 > 搭配 [Leetcode 解題系統](https://leetcode.com/) ## > 上一章：[回溯法](https://hackmd.io/s/B1Q0_-whQ) > 下一章：[Stack與Queue](https://hackmd.io/s/BkZaF56Cm) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z) ## 二分搜尋法的用途 玩過終極密碼嗎? 對方心裡想一個數字，每當你猜一次他都要告訴你該往更高還是更低猜聰明的你會知道，既然對方會告訴你該更高還更低那麼想要盡快猜出答案時絕不是慢慢從1和2一個一個猜上去而是每次都猜中間值讓每一輪都可以從他的指引淘汰掉一半的可能同樣的方法也可以用在很多問題上只要那個問題有以下的性質 1. 他的解是整數 2. 猜錯時可以明確知道該往更高還是更低猜那麼就可以使用這種每次對半砍的技法來讓尋找答案的步驟一次就降到$log_2^N$ ## 如何使用二分搜尋法 【例題】 > 給一個由小到大排序好且長度為 10 的陣列 > 請問數字 48 在陣列的第幾格? ![](https://i.imgur.com/2yN4nwE.png) 我們很容易就能用眼睛判斷出它在第 6 格而電腦程式必須一格一格確認才能知道它在哪裡但既然已經知道陣列是從小到大排列好的我們就可以不需要每格都確認而是用二分搜尋法來尋找一開始從第 0 格到第 9 格都是可能的答案因此我們有 ```cpp= int left = 0; int right = 9; ``` 然後我們可以看看「中間」的位置，是不是我們要的答案呢？ ```cpp= int mid = (left+right)/2; // mid = 4 ``` ![](https://i.imgur.com/vkKbbOc.png) 我們發現第 4 格的數字是 29 小於我們要找的 48 這時我們不但能確定第 4 格不是我們要的答案連同第 4 格以前的所有格子都不會是我們要的答案了！因此我們可以把 left 移到第 5 格代表現在開始可能的範圍是第 5 格至第 9 格 ```cpp= if(arr[mid]<48) left = mid+1; // left = 5 ``` 這時新的「中間」的位置，是不是我們要的答案呢？ ```cpp= int mid = (left+right)/2; // mid = 7 ``` ![](https://i.imgur.com/0fJVmD9.png) 我們發現第 7 格的數字是 49 大於我們要找的 48 這時我們不但能確定第 7 格不是我們要的答案連同第 7 格以後的所有格子都不會是我們要的答案了！因此我們可以把 right 移到第 6 格代表現在開始可能的範圍是第 5 格至第 6 格 ```cpp= if(arr[mid]>48) right = mid-1; // right = 6 ``` 這時新的「中間」的位置，是不是我們要的答案呢？ ```cpp= int mid = (left+right)/2; // mid = 5 ``` ![](https://i.imgur.com/gWOa78V.png) 我們發現第 5 格的數字是 32 小於我們要找的 48 這時我們不但能確定第 5 格不是我們要的答案連同第 5 格以前的所有格子都不會是我們要的答案了！因此我們可以把 left 移到第 6 格代表現在開始可能的範圍是第 6 格至第 6 格 ```cpp= if(arr[mid]<48) left = mid+1; // left = 6 ``` 這時新的「中間」的位置，是不是我們要的答案呢？ ```cpp= int mid = (left+right)/2; // mid = 6 ``` ![](https://i.imgur.com/SFmdAWg.png) 我們終於在第六格找到所要的 48 可以印出答案了 ```cpp= if(arr[mid]==48) cout << "48 is at "<<mid<<endl; ``` 把剛才出現過的程式都組合起來就是以下的樣子 ```cpp= int left = 0; int right = 9; while(true){ // 找到為止 int mid = (left+right)/2; // 取範圍的中間 if(arr[mid]<28){ // 如果 mid 太小，就把下界縮到 mid+1 left = mid+1; } else if(arr[mid]>28){ // 如果 mid 太大，就把上界縮到 mid-1 right = mid-1; } else{ cout << "找到了!" << endl; break; } } ``` 你也可以自行推演看看不管想要找的目標在陣列的哪一格依據這樣的程式都能正確找出來 【學生練習題】 > - [ ] [Leetcode 374: 猜數字 ](https://leetcode.com/problems/guess-number-higher-or-lower/) > > 對方從1到n的範圍選了一個數字，我們要猜出是什麼數字 > 我們可以呼叫函數 guess(x) 來問他 x 是不是答案 > 如果 x 太大了，他會回傳 -1 > 如果 x 太小了，他會回傳 1 > 如果 x 就是答案，他會回傳 0 來告訴我們 > 我們要回傳找到的答案注意：在計算中間值 `(left+right)/2` 的時候 `(left+right)` 可能會超出整數範圍導致出現錯誤的數字因此我們可以算成 `left+(right-left)/2` 結果是一樣的，但可以保證不超出整數範圍不過剛才示範的這個二分搜尋的用途太狹隘了其實二分搜尋的用途應該要是很廣泛的！我們稍微把題目變化一下，像是： 【例題】 > 給一個由小到大排序好且長度為 10 的陣列 > 請問數字 50 在不在陣列裡呢? 【例題】 > 給一個由小到大排序好且長度為 10 的陣列 > 請問第一個「大於」33 的數字在陣列的第幾格? 【例題】 > 給一個數字 N > 求出讓 a\*a 大於 N 的最小 a > (不使用 sqrt() 函數) 像這樣千變萬化的題目用剛才的方法很容易就會把程式寫得花花綠綠亂七八糟還有各種硬加上去的判斷式都難以確定是否涵蓋所有可能因此這裡提供一個萬用的二分搜尋模板！你可以依據題目的性質把在模板上填入相對應的值並依據題目的性質處理搜到的答案這樣一來不管什麼變化的二分搜尋法都能萬無一失了！ ## 二分搜尋法的模板 - 找第一個「夠大」的 ```cpp= int left = 最小可能的答案 int right = 最大可能的答案 while(left<right){ int mid = (left+right)/2; if(mid 太小了){ left = mid+1; } else{ // mid 沒有太小 right = mid; // 注意是 mid，不是 mid-1 喔 // 因為此時 mid 並沒有太大，僅只是沒有太小而已 // 也就是說此時的 mid 有可能是答案，我們不剃除它 } } // 迴圈結束後，left會等於right // 這時 left 就會是「第一個」「沒有太小」的位置 // 再依據題目要求來把 left 換算成答案 ``` 我們來用幾個例題示範看看這個模板 【例題】 > 給一個由小到大排序好且長度為 10 的陣列 > 請問第一個「大於」33 的數字在陣列的第幾格? ![](https://i.imgur.com/F5bvloH.png) 如果是上圖所示的陣列的話，所求的結果應該要是第 6 格我們先來想想在這個題目中最小可能的搜尋結果、最大可能的搜尋結果，分別是多少？先來看看最小的可能：如果整個陣列的值都大於33，例如 `[35, 40, 45, 48, 60, 63, 69, 78, 99, 100]` 那麼答案應該要是 0 (第一個大於33個數字在第0格) 再來看看最大的可能：如果整個陣列的值都小於等於33，例如 `[6, 9, 12, 15, 18, 21, 24, 27, 30, 33]` 那麼「第一個大於 33」的位置應該要在哪裡呢？由於陣列裡面根本沒有東西大於33 所以我們希望二分搜尋的結果是一個不存在的位置來讓我們知道「大於33個數字不存在」我們可以用「最後一格的下一格(也就是第10格)」來表示這個結果換個角度想「第n格是第一個大於33的格子」就相當於「總共有n個格子是小於等於33的」所以當全部10個數字都小於等於33時宣稱「第10格是第一個大於33的格子」也挺合理的因此在這題裡面「最小可能的結果」是 0 「最大可能的結果」是 10 而「mid太小」的定義為 arr[mid]<=33 (因為我們要找第一個大於33 的數字) 因此套上模板後程式會是 ```cpp= int left = 0; int right = 10; while(left<right){ int mid = (left+right)/2; if(arr[mid]<=33){ left = mid+1; } else{ // arr[mid]>33 right = mid; } } // 迴圈結束後，left會等於right // 這時 left 就會是「第一個大於33」的位置 if(left==10){ cout << "There isn't any element in the array larger than 33" << endl; } else{ cout << "The first element larger than 33 is at " << left; cout << ", which is " << arr[left] << endl; } ``` 你也可以自行推演看看當目標改成大於其他數字時這支程式是不是也能正確地找出位置你也可以試試看如果目標要找的數字比陣列裡任何其他數字都大時 left 和 right 是不是會正確地停在 10 的位置呢？要注意的是當`left==right` 發生時，迴圈就會結束了 **因此 mid 永遠不會有機會等於 right** 所以儘管我們的 right 一開始等於10 我們也無須擔心程式會企圖存取陣列的第10格 【例題】 > 題目給一個由小到大排序好的陣列 nums 和一個數字 target > 請問 target 在 nums 裡的第幾個位置呢？ > 如果 target 不在 nums 裡，請回傳 -1 這是 Leetcode 上的題目，連結是 [Leetcode 704](https://leetcode.com/problems/binary-search/) 這題可以用和上一題完全相同的做法也就是找找看「第一個『大於等於target』的數字在陣列的第幾格」再看看那一格是不是 target 就知道陣列裡面有沒有 target 了 ```cpp= int left = 0; int right = nums.size(); while(left<right){ int mid = left + (right-left)/2; if(nums[mid]<target){ // 要找 >=target 的位置，所以 <target 是太小 left = mid+1; } else{ // nums[mid]>=target right = mid; } } // 迴圈結束後，left會等於right // 這時 left 就會是「第一個大於等於target」的位置 if(left==nums.size()||arr[left]!=target) return -1; else return left; ``` 【學生練習題】 > - [ ] [Leetcode 35: 數字該在哪裡插入 ](https://leetcode.com/problems/search-insert-position/) > > 給一個從小排到大的陣列 nums 和一個整數 target > 請問 target 在 nums 裡的哪個位置呢？ > 如果不在，我們可以將 target 插入 nums 裡的哪個位置，能保持 nums 依照小到大排好呢？提示：尋找第一個「大於等於」 【學生練習題】 > - [ ] [Leetcode 744: 第一個夠大的字母 ](https://leetcode.com/problems/find-smallest-letter-greater-than-target/) > > 給一個從小排到大的字元型態的陣列 letters 和一個字元 target > 請找出第一個比 target 還要大 (b比a大，c比b大...以此類推) 的字元 > 如果 letters 裡的所有字元都不比 target 大，則回傳 letters[0] 提示：字元可以直接比大小 `if(letters[mid]<target) ...` ## 找最後一個「夠小」的 【例題】 > 給一個由小到大排序好且長度為 10 的陣列 > 請問最後一個「小於」49 的數字在陣列的第幾格? 要找「最後一個**小於**49的數字」我們可以用上面的模板找「第一個**大於等於**49的數字」在哪裡！找到之後只需要把找到的位置再「往前」一格就會是我們要的「最後一個小於49的數字」了！ ![](https://i.imgur.com/F5bvloH.png) ```cpp= int left = 0; int right = 10; while(left<right){ int mid = (left+right)/2; if(arr[mid]<49){ left = mid+1; } else{ // arr[mid]>=49 right = mid; } } // 迴圈結束後，left會等於right // 這時 left 就會是「第一個大於等於49」的位置 // 而 left-1 就會是「最後一個小於49」的位置 cout << "The last element smaller than 49 is at " << left-1; cout << ", which is " << arr[left-1] << endl; ``` 模板真是萬用！你也可以試試看如果目標要找的數字比陣列裡任何其他數字都小時會發生什麼事？例如找「最後一個小於3的數字」那麼在迴圈結束後 left 和 right 會等於 0 (因為第一個大於等於3個數字在第0格) 於是 left-1 會是「-1」由於陣列根本就沒有第 -1 格那麼「最後一個小於3的數字在陣列的第-1格」代表什麼意思呢？就代表「陣列裡的數字全部都沒有小於3 」！ ## 二分搜尋法的進階題 - 找最小值 二分搜尋法當然不只能在陣列中找東西也可以解決很多運算問題舉例來說，在某些找最小值的題目裡我們可以用二分搜尋法找「第一個夠大的」 【例題】 > 資訊課本有若干個章節，每個章節有不同的若干頁，用nums表示 > nums[0]代表第0章有幾頁，nums[1]代表第1章有幾頁，以此類推 > 到期末還剩下 threshold 堂課 > 老師和同學們要共同決定一個上課速率（每堂課上幾頁） > 必須保證到期末之前能夠上完整本課本，且一堂課內不跨章節 > 請問至少要有每堂課幾頁的速率？ > > 注意一堂課內不跨章節，也就是如果那堂課已經把某章節講完了，就要提早下課，不能提早進入下一章舉例來說，課本有4章，分別是1, 2, 5, 9頁，到期末前還有6堂課 - 如果一堂課上4頁 - 第 0 章要花一堂課才能上完 1 頁 - 第 1 章要花一堂課才能上完 2 頁 - 第 2 章要花兩堂課才能上完 5 頁 - 第 3 章要花三堂課才能上完 9 頁 - 因此總共要7堂課才夠上，這個速率不夠大 - 如果一堂課上5頁 - 第 0 章要花一堂課才能上完 1 頁 - 第 1 章要花一堂課才能上完 2 頁 - 第 2 章要花一堂課才能上完 5 頁 - 第 3 章要花兩堂課才能上完 9 頁 - 因此總共要5堂課就夠上，這個速率夠大 - 如果一堂課上6頁 - 第 0 章要花一堂課才能上完 1 頁 - 第 1 章要花一堂課才能上完 2 頁 - 第 2 章要花一堂課才能上完 5 頁 - 第 3 章要花兩堂課才能上完 9 頁 - 因此總共要5堂課就夠上，這個速率夠大根據上述觀察，第一個夠大的速率是一堂課上5頁，因此答案是5 我們可以利用二分搜尋法找出「第一個夠大的速率」在解題的過程中，我們會需要一個函數來幫忙判斷「這個速率夠大嗎？」 ```cpp= // 算 a/b 的無條件進位到整數 int divide(int a, int b){ return (a-1)/b + 1; } // 檢驗 speed 夠不夠大 bool is_speed_enough(vector<int> pages, int given_classes, int speed){ // 算這個速率需要幾堂課才能上完 int needed_classes = 0; for(int i=0;i<pages.size();i++){ needed_classes += divide(pages[i], speed); } // 檢查需要的課堂數是否小於等於我們擁有的課堂數 if(needed_classes <= given_classes) return true; else return false; } ``` 有了上面這個幫助檢驗「上課速率是否夠大」的函數我們就可以用二分搜尋法找「第一個夠大」的速率 ```cpp= int left = 1; // 至少要上一頁吧 int right = 1000000; // 題目說了，一章最多一百萬頁，所以我們一堂課至多就是一百萬頁 while(left<right){ int mid = left+(right-left)/2; if(!is_speed_enough(nums, threshold, mid)) // 速率太小 left = mid+1; else // 速率夠大 right = mid; } return left; ``` 以上是 Leetcode 上的題目，連結是 [Leetcode 1283](https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/) 【學生練習題】 > - [ ] [Leetcode 875: 猴子吃香蕉 ](https://leetcode.com/problems/koko-eating-bananas/) > > 有若干堆香蕉，每堆有不同的若干根香蕉，用名為 piles 的陣列表示 > 農場主人再過 h 小時就會回來了 > 猴子希望在這段時間內把香蕉通通吃完 > 請幫猴子決定一個吃香蕉的速率 > 既吃得完，又盡可能吃得慢（最小吃得完的速率）提示：這題和例題簡直一模一樣唯一不同的是香蕉最多有十億（1000000000）根所以要把搜尋的範圍擴大到十億 【例題】 > 船要在`day`天內運輸完所有的貨物 > 每件貨物重量不同，他們的重量依序用陣列 `weights` 來表示 > 請問船的承重至少要是多少 > 才能在 `day` 天內把所有貨物依序運輸完？舉例來說，貨物重量分別是 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，共有5天 - 如果船的承重是14，則 - 第一天運 [1, 2, 3, 4] （不能再把5放進來了，會超重） - 第二天運 [5, 6]（不能再把7放進來了，會超重） - 第三天運 [7]（不能再把8放進來了，以下類推） - 第四天運 [8] - 第五天運 [9] - 第六天運 [10] - 可知 5 天內運不完 - 如果船的承重是15，則 - 第一天運 [1, 2, 3, 4, 5] （不能再把6放進來了，會超重） - 第二天運 [6, 7]（不能再把8放進來了，會超重，以下類推） - 第三天運 [8] - 第四天運 [9] - 第五天運 [10] - 由此可知 5 天內可運完由以上觀察可知船至少要有 15 的承重才能在 5 天內運完我們可以用二分搜尋找出「第一個夠大的承重量」需要準備寫一個函數幫忙判斷「船的承重是否夠大」 ```cpp= bool ship_enough(const vector<int>& weights, int days, int capacity){ int day_used = 0; // 需要的天數 int current_weight = 0; // 目前裝了多少重量 for(int i=0;i<weights.size();i++){ // 如果船裝不下第i件貨物了 if(current_weight+weights[i]>capacity){ day_used++; // 先把目前的運走，明天再來運這件貨 current_weight = 0; // 明天就是一艘清空後的船 } // 如果空船都放不下這件貨，直接判定船不夠大 if(weights[i]>capacity) return false; current_weight+=weights[i]; // 把貨物重量加到當前船裝載的重量上 } day_used++; // 最後一天也要算進去 if(day_used<=days) return true; // 可以在 days 天內載完 else return false; // 不能 } ``` 有了這個函數的幫忙，我們就可以用二分搜尋法 ```cpp= int left = 1; int right = 25000000; // 所有貨加起來至多重 500*50000 while(left<right){ int mid = left+(right-left)/2; if(!ship_enough(weights, days, mid)) // 船不夠大 left = mid+1; else right = mid; // 船夠大 } return left; ``` 以上是 Leetcode 上的題目，連結是 [Leetcode 1011](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/) 【學生練習題】 > - [ ] [Leetcode 1760: 最大袋的球可以多小 ](https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/) > > 有若干袋球，每一袋有不同數量的若干顆球，用陣列 nums 表示 > 我們可以選一袋球把它一分為二，例如一袋5顆可以變成1+4或2+3 > 這樣的操作，至多可以做 maxOperations 次 > 我們的目標是讓操作完畢後最大的一袋「盡可能的小」 > 請問它可以是多小？提示：找第一個夠大的球數，搭配函數檢驗「這個球數夠大嗎？」：如果我們無法用 maxOperations 次切割來達成這個大小，就代表他太小了 【學生練習題】 > - [ ] [Leetcode 1482: 最早哪天夠做花束 ](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/) > > 花園裡有若干朵花，每朵花盛開的日子不同，用陣列 bloomDay 表示 > 每做一個花束，我們需要採已經盛開的花 k 朵，且要是陣列裡連續的 k 朵 > 盛開的花不會謝，但花採了一次就不能再採了 > 我們總共需要 m 個花束 > 請問最早哪一天，花能開到夠做 m 個花束的程度？提示：找第一個夠大的天數，搭配函數檢驗「這一天已開了的花夠做 m 個花束嗎」 ## 二分搜尋法的進階題 - 找最大值 和找最小值類似在某些找最大值的題目裡我們可以用二分搜尋法找「最後一個夠小的」 【例題】 > 給一個數字 N > 請問 N 開根號後的整數部分是多少？如果 N 是 3，那麼 $\sqrt N$ 的整數部分就是 1 如果 N 是 10，那麼 $\sqrt N$ 的整數部分就是 3 如果 N 是 0，那麼 $\sqrt N$ 的整數部分就是 0 我們要找的是「最後一個平方不大於N」的數字根據模板也就是要找「第一個平方大於N」的數字再將他減一即為答案要找「第一個平方大於N的數字」我們可以大概知道最小可能的答案是1 最大可能的答案是N+1 因此可以令 left 和 right 分別為 1 和 N+1 ```cpp= int left = 1; int right = N+1; while(left<right){ int mid = left + (right-left)/2; if(mid*mid<=N){ left = mid+1; } else{ // mid*mid>N right = mid; } } // 迴圈結束後，left會等於right // 這時 left 就會是「第一個平方大於N」的數字 // 而 left-1 就會是「最後一個平方不大於N」的位置 cout << "the integer part of the square root of N is " << left-1; ``` 你可以測試看看當 N 等於 3, 10, 或 0 的時候出來的答案是不是都是對的呢？以上是 Leetcode 上的題目，連結是 [Leetcode 69](https://leetcode.com/problems/sqrtx/) 有一點麻煩的地方是題目的 N 至多為 $2^{31}-1$，所以 N+1 會超出整數範圍解決方法是在宣告變數的時候，用 long long 來取代 int 【學生練習題】 > - [ ] [Leetcode 367: 完全平方數 ](https://leetcode.com/problems/valid-perfect-square/) > > 給一個整數 num，請問他是完全平方數嗎？可以用例題的方法做，最後檢驗是不是`(left-1)*(left-1)==num` 【學生練習題】 > - [ ] [Leetcode 441: 擺放錢幣 ](https://leetcode.com/problems/arranging-coins/) > > 我們有 n 個硬幣 > 第一排放1個硬幣 > 第二排放2個硬幣，一直到把n個硬幣全部用完 > 請問最後一個「一整排都有硬幣的一排」是哪一排？ > ![image](https://hackmd.io/_uploads/Hy9Qhojua.png) > 如上圖，5個硬幣，最後完整的一排是第2排 > > ![image](https://hackmd.io/_uploads/HkFBhsou6.png) > 如上圖，8個硬幣，最後完整的一排是第3排提示：相當於找最大的 k 使得 $(1+k)*k/2<=n$ (三角形數公式) 【例題】 > 有若干種糖果，每一種都有其價格，用陣列 price 表示 > 我們要從裡面挑 k 個來組成美味糖果籃 > 糖果籃子的美味程度是價格最接近的兩種糖果的價差 > 請問盡可能美味的糖果籃子有多美味？例如糖果的價格是 [13, 5, 1, 8, 21, 2] 而我們要挑 3 顆我們可以挑 [13, 5, 21] 這樣美味程度就是 8 （正好 21-13 和 13-5 都是 8）美味程度太大，我們就挑不出 k 顆糖果來美味程度夠小才可以，但我們希望盡量美味我們可以用二分搜尋法找「最後一個夠小的美味程度」也就是「第一個太大的美味程度」減一我們需要寫一個函數幫忙檢查「是不是要求太美味了（讓我們無法挑出k顆糖果）」 ```cpp= bool TooTasty(vector<int> price, int k, int diff){ // diff 是價差也就是美味程度 // 我們可以先選最便宜的糖果，然後剩下的糖果從便宜的到貴的一一確認 // 第一個價差夠大的就可以也選起來，重複此過程，就能盡可能選出最多糖果 // // 第一顆（最便宜那顆）必選 int selected = 1; int last = price[0]; for(int i=1;i<price.size();i++){ // 如果第 i 顆糖果跟上一個入選的糖果價差太小，就不選第i顆 if(price[i]-last<diff) continue; // 反之，把第 i 顆選起來 selected++; last = price[i]; } if(selected < k) return true; // 是個讓人選不出 k 顆的美味程度 else return false; // 要求不夠高，還能選出 k 顆 } ``` 有了這個函數的幫忙，我們就能完成二分搜尋 ```cpp= sort(price.begin(), price.end()); // 記得先把糖果依照價格從小到大排序好！ int left = 1; int right = 1000000000; // 糖果價格的上限 while(left<right){ int mid = left + (right-left)/2; if(!TooTasty(price, k, mid)) left = mid+1; else right = mid; } // left 是「第一個太大的美味程度」讓我們無法選出k顆 return left-1; // 所以 left-1 就是「最後一個夠小的美味程度」，能選出k顆且最盡可能美味 ``` 以上是 Leetcode 上的題目，連結是 [Leetcode 2517](https://leetcode.com/problems/maximum-tastiness-of-candy-basket/) 【學生練習題】 > - [ ] [Leetcode 1552: 球之間的磁力可以多大 ](https://leetcode.com/problems/magnetic-force-between-two-balls/) > > 有若干個球桶，他們在數線上的位置用陣列 position 表示 > 我們要從中挑 m 個桶子放入 m 顆球 > 此系統造成的磁力為距離最近的兩顆球的距離 > 請問可以造成的最大磁力為多少這一題和例題簡直一模一樣，連上限也正好是10^9 【學生練習題】 雖然是 codeforces 的題目但因為很有趣所以留下來了 > - [ ] [CF911B - Two Cakes](https://codeforces.com/problemset/problem/911/B) > > 派對共準備了a片鹹蛋糕和b片甜蛋糕 > 來參加派對的人總共有n位 > 因此你要把這些蛋糕分配到n個盤子上 > > 每個盤子上都可以有任意多片鹹蛋糕 > 或是任意多片甜蛋糕 > 但是不能一個盤子上又有鹹又有甜 > > 當你分配完後 > 「最少片蛋糕」的那個盤子會歸你 > 你希望你可以吃多一點蛋糕，因此你會盡量平均分配 > 請問在你的努力之下，你可以吃多少片呢？我們來分析一下這個問題： - 如果你能吃到 1 片，代表裝鹹蛋糕的盤子不能超過 a 個；裝甜蛋糕的盤子不能超過 b 個 - 如果你能吃到 2 片，代表裝鹹蛋糕的盤子不能超過 a/2 個；裝甜蛋糕的盤子不能超過 b/2 個 $\vdots$ - 如果你能吃到 x 片，代表裝鹹蛋糕的盤子不能超過 a/x 個；裝甜蛋糕的盤子不能超過 b/x 個換句話說，要是 a/x+b/x 小於 n，代表你無法吃到 x 片！因此你要搜尋的是「第一個你吃不到的數量」再減1即是答案也就是搜尋「第一個符合 a/x+b/x<n 的 x」 (提示：最小可能的值是1，最大可能的值是max(a, b)+1) ## > 上一章：[回溯法](https://hackmd.io/s/B1Q0_-whQ) > 下一章：[Stack與Queue](https://hackmd.io/s/BkZaF56Cm) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)