# 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) ## <font color='darkblue'>二分搜尋法的用途</font> 玩過終極密碼嗎? 對方心裡想一個數字,每當你猜一次 他都要告訴你該往更高還是更低猜 聰明的你會知道,既然對方會告訴你該更高還更低 那麼想要盡快猜出答案時 絕不是慢慢從1和2一個一個猜上去 而是每次都猜中間值 讓每一輪都可以從他的指引淘汰掉一半的可能 同樣的方法也可以用在很多問題上 只要那個問題有以下的性質 1. 他的解是整數 2. 猜錯時可以明確知道該往更高還是更低猜 那麼就可以使用這種每次對半砍的技法 來讓尋找答案的步驟一次就降到$log_2^N$ ## <font color='darkblue'>如何使用二分搜尋法</font> <font color='darkorange'>【例題】</font> > 給一個由小到大排序好且長度為 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; } } ``` 你也可以自行推演看看 不管想要找的目標在陣列的哪一格 依據這樣的程式都能正確找出來 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [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` 結果是一樣的,但可以保證不超出整數範圍 不過剛才示範的這個二分搜尋的用途太狹隘了 其實二分搜尋的用途應該要是很廣泛的! 我們稍微把題目變化一下,像是: <font color='darkorange'>【例題】</font> > 給一個由小到大排序好且長度為 10 的陣列 > 請問數字 50 在不在陣列裡呢? <font color='darkorange'>【例題】</font> > 給一個由小到大排序好且長度為 10 的陣列 > 請問第一個「大於」33 的數字在陣列的第幾格? <font color='darkorange'>【例題】</font> > 給一個數字 N > 求出讓 a\*a 大於 N 的最小 a > (不使用 sqrt() 函數) 像這樣千變萬化的題目 用剛才的方法很容易就會把程式寫得花花綠綠亂七八糟 還有各種硬加上去的判斷式 都難以確定是否涵蓋所有可能 因此 這裡提供一個萬用的二分搜尋模板! 你可以依據題目的性質 把在模板上填入相對應的值 並依據題目的性質處理搜到的答案 這樣一來 不管什麼變化的二分搜尋法都能萬無一失了! ## <font color='darkblue'>二分搜尋法的模板 - 找第一個「夠大」的</font> ```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 換算成答案 ``` 我們來用幾個例題示範看看這個模板 <font color='darkorange'>【例題】</font> > 給一個由小到大排序好且長度為 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格 <font color='darkorange'>【例題】</font> > 題目給一個由小到大排序好的陣列 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; ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Leetcode 35: 數字該在哪裡插入 ](https://leetcode.com/problems/search-insert-position/) > > 給一個從小排到大的陣列 nums 和一個整數 target > 請問 target 在 nums 裡的哪個位置呢? > 如果不在,我們可以將 target 插入 nums 裡的哪個位置,能保持 nums 依照小到大排好呢? 提示:尋找第一個「大於等於」 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [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) ...` ## <font color='darkblue'>找最後一個「夠小」的</font> <font color='darkorange'>【例題】</font> > 給一個由小到大排序好且長度為 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 」! ## <font color='darkblue'>二分搜尋法的進階題 - 找最小值</font> 二分搜尋法當然不只能在陣列中找東西 也可以解決很多運算問題 舉例來說,在某些找最小值的題目裡 我們可以用二分搜尋法找「第一個夠大的」 <font color='darkorange'>【例題】</font> > 資訊課本有若干個章節,每個章節有不同的若干頁,用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/) <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Leetcode 875: 猴子吃香蕉 ](https://leetcode.com/problems/koko-eating-bananas/) > > 有若干堆香蕉,每堆有不同的若干根香蕉,用名為 piles 的陣列表示 > 農場主人再過 h 小時就會回來了 > 猴子希望在這段時間內把香蕉通通吃完 > 請幫猴子決定一個吃香蕉的速率 > 既吃得完,又盡可能吃得慢(最小吃得完的速率) 提示:這題和例題簡直一模一樣 唯一不同的是香蕉最多有十億(1000000000)根 所以要把搜尋的範圍擴大到十億 <font color='darkorange'>【例題】</font> > 船要在`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/) <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Leetcode 1760: 最大袋的球可以多小 ](https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/) > > 有若干袋球,每一袋有不同數量的若干顆球,用陣列 nums 表示 > 我們可以選一袋球把它一分為二,例如一袋5顆可以變成1+4或2+3 > 這樣的操作,至多可以做 maxOperations 次 > 我們的目標是讓操作完畢後最大的一袋「盡可能的小」 > 請問它可以是多小? 提示:找第一個夠大的球數,搭配函數檢驗「這個球數夠大嗎?」:如果我們無法用 maxOperations 次切割來達成這個大小,就代表他太小了 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Leetcode 1482: 最早哪天夠做花束 ](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/) > > 花園裡有若干朵花,每朵花盛開的日子不同,用陣列 bloomDay 表示 > 每做一個花束,我們需要採已經盛開的花 k 朵,且要是陣列裡連續的 k 朵 > 盛開的花不會謝,但花採了一次就不能再採了 > 我們總共需要 m 個花束 > 請問最早哪一天,花能開到夠做 m 個花束的程度? 提示:找第一個夠大的天數,搭配函數檢驗「這一天已開了的花夠做 m 個花束嗎」 ## <font color='darkblue'>二分搜尋法的進階題 - 找最大值</font> 和找最小值類似 在某些找最大值的題目裡 我們可以用二分搜尋法找「最後一個夠小的」 <font color='darkorange'>【例題】</font> > 給一個數字 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 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Leetcode 367: 完全平方數 ](https://leetcode.com/problems/valid-perfect-square/) > > 給一個整數 num,請問他是完全平方數嗎? 可以用例題的方法做,最後檢驗是不是`(left-1)*(left-1)==num` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [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$ (三角形數公式) <font color='darkorange'>【例題】</font> > 有若干種糖果,每一種都有其價格,用陣列 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/) <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Leetcode 1552: 球之間的磁力可以多大 ](https://leetcode.com/problems/magnetic-force-between-two-balls/) > > 有若干個球桶,他們在數線上的位置用陣列 position 表示 > 我們要從中挑 m 個桶子放入 m 顆球 > 此系統造成的磁力為距離最近的兩顆球的距離 > 請問可以造成的最大磁力為多少 這一題和例題簡直一模一樣,連上限也正好是10^9 <font color="darkgreen"> 【學生練習題】</font> 雖然是 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)