二分法

最近做了幾道關於二分法的題目，覺得比較典型，因此拿出來說一說。

首先，先把題目分享一下。

題目描述：上題中講了一個故事，故事大意不用過多關註，有用部分為：某地主有一個大糧倉，這個糧倉容量為 n 個單位，但這個糧倉有個小口，每天會有一部分麻雀過來偷吃糧食，同時地主每天也會從別的地方運來糧食填補。開始的時候糧倉是滿的，麻雀偷吃和運量的具體信息如下：

1⃣️從第一天開始，每天會有麻雀過來吃糧食，第 i 天會來 i 只麻雀，每隻麻雀吃一個單位的糧食。

2⃣️從第二天開始，地主每天會從別的地方運來 m 個單位的糧食加入到糧倉中，由於糧倉的總容量是 n ，因此運來的糧食填滿糧倉後多餘的糧食扔掉。

題目要求，求出第幾天糧倉第一次空了。

針對這個過程舉例如下

上文意思是：假設糧倉容量 n 為 5 ，每天運糧數量為 2 ，那麼

開始之前，糧倉里有5 個單位的糧食，糧倉是滿的。

第一天 ，來了一隻麻雀，吃了 1 單位的糧食，因此在第一天結束的時候，糧倉里剩餘4單位的糧食。

第二天，地主先運來 2 單位的糧食來填補糧倉，由於 n ＝ 5 ，第一天剩餘 4 ，現在運來  2 單位，所以 添進糧倉 1 單位後，有1 單位浪費掉。此時糧倉里有 5 單位的糧食（糧倉是滿的）。填充完畢後，來了 2 只麻雀，吃掉 2 個單位的糧食，此時糧倉里剩餘 3 個單位的糧食。

第三天，地主又運來 2 單位的糧食，將只有 3 個單位糧食的糧倉再次填滿，這次沒有浪費，填充完畢，飛來 3 只麻雀，吃掉 3 單位的糧食，此時糧倉里剩餘 2  個單位的糧食。

第四天，地主運來 2 個單位的糧食，加入 原來剩餘 2 單位糧食後，這時，糧倉里只有 4 單位的糧食，沒有填滿。填充完畢，飛來 4 只麻雀，吃掉 4 個單位的糧食，這時候糧倉空了。

因此，答案即為 4 。

題目的輸入輸出格式以及測試數據如下

請務必認真仔細的記住題目中所給的數據範圍。

根據題目的介紹，可以發現，這道題首先可以分成兩種情況，

1⃣️ n < m 時，第一天 ，1 只麻雀吃過後剩 n － 1 糧食，第二天開始，運來 m 單位的糧食，將糧倉填滿為 n ，第二天結束， 2 只麻雀吃過後剩 n － 2 糧食，在第三天開始時，運來的m糧食又將 糧倉填滿為 n ，。 。 。直到 第 n － 2 的時候，n － 2 只麻雀吃過後，剩餘 2 糧食，第 n － 1 天開始時，運來 m 單位糧食（ m > n ），因此又將糧倉填滿為 n ，飛來 n － 1 只麻雀，吃過後，糧倉 剩餘 1 糧食，第 n 天開始，地主運來的 m 單位糧食又把糧倉填滿了，這時飛來 n 只麻雀，正好吃完了 n 單位糧食，因此糧倉就空了 ，（題目要求一旦糧倉空了，就停止計算，不給地主接下來一天運來糧食的機會）由此可以看出，在這種情況中，糧倉吃空需要的天數就是糧倉的總容量 n 。

2⃣️ n > m 時，在前 m 天，麻雀吃掉的糧食都能在第二天的時候補上，但到第 m ＋ 1 天的時候，麻雀吃掉 m ＋ 1糧食，在第 m ＋ 2 的時候運來的 m 糧食 無法將 糧倉填滿。也就是說，從第 m ＋ 1 天開始，第 i 天糧倉的存糧數目在前一天的基礎上減少 i 個單位，假設 在 第 m ＋ k 天將糧食吃完了，那麼從 第 m ＋ 1 天開始計算，在 第 m ＋k － 1天結束的時候，就滿足 

(1+m) ＋ (2+m) ＋ (3+m) ＋。。。＋（k－1+m）+ < （n－m） +(k-1)＊m,

在 第m ＋ k 天結束的時候，就滿足

（1+m）＋（2+ m）＋。。。＋（k＋m）>＝（n－m）＋k＊m。

現在，可以將這個過程進行進一步化簡：

在m天之後，假設加完糧食後糧倉現在有糧食 x 個單位，天數是第 m ＋ i 天，現在把整個糧倉分為兩部分，一部分有糧食 m單位，另一部分有糧食 x－m 個單位，把飛來的 麻雀也分為兩部分，一部分 有麻雀 m 只，另一部分 有麻雀 i 只，要求 m 只麻雀吃 m 個糧食的那部分，i 只麻雀去吃 x－m 的那部分糧食，那麼m只麻雀 每天總能 和運來的 m 單位糧食相抵消，剩餘的 x－m 那部分糧食會不斷減少，直至吃光。也就意味著在 m＋1到 m＋i 這 i 天，每天 除去 m只剩餘的麻雀 加起來吃掉的就是第 m 天 結束的時候 剩餘的那部分糧食。m天結束的時候剩餘的糧食為 n－m ，

假設在第 m＋k 天時候來的麻雀吃光了剩餘的糧食。因此除去每天抵消的那部分，剩餘的麻雀吃到糧食的總數為 n－m。有等式如下

1+2+3＋。。。＋k >= n - m ,

（這裡用  >=  的原因是，在第 m ＋k 天的時候，不一定所有來的麻雀都剛好有糧食吃，因此麻雀數有可能比剩餘糧食數多）

並且，在 k－1天的時候，來的麻雀並沒有將剩餘的糧食吃完。滿足

1+2+3 。。。＋（k－1）< n-m .

之所以要將方法進一步精簡的原因是，題目給的測試數據 是 long long ，第一種方法多加的 k 個m 增大了數據，是有可能導致爆掉 long long 的一個原因。反觀第二種思路，數據減小了不少，會減小這個風險，但是本質上來講是沒有區別的，因為他們是屬於同一量級的數據

第一種思路 不等式左邊為

（1+m）＋（2+ m）＋。。。＋（k＋m）＝k＊m＋（1+k）＊k／2＝k＊m＋k／2+k＊k／2（包含k的二次方項）

第二種思路不等式左邊為

1+2＋3+。。。＋k ＝（1+k）＊k／2=k／2+k＊k／2（同樣包含k的二次方項）

由於 天數 m 和 n 都是 long long 類型的，那麼 k 也必然是 long long 類型的，如果數據給的是 long long 的上限，那麼，二次方必然會超出上界。而且，做為一組優秀的測試數據，應該包含這樣的邊界數據來檢測程式的穩定性。

採用上面的判斷條件來找 k ，只要數據足夠大，閉著眼睛也能將 long long 爆掉，那是不是就意味著 這個方法行不通呢？並非如此，上面的思路是非常精簡的一個思路了。那就在 k 的數據範圍上做文章，k 的最大範圍肯定是 大於1 而小於 n＋m 的，假設 m 和 n 的數據為 1e18 量級，那麼加和之後 數據為1e19 量級，由不等式 （1+k）＊k／2=k／2+k＊k／2＝1+2+3＋。。。＋k >= n - m 可知，k＊k 的數據為1e19 的量級的，則 k的量級最大界限變為 1e10。這樣就穩了。

既然選對了方向，接下來就是 找這個 k 值了，最簡單的想法是加一層迴圈從第一天到第 n＋m 天逐個判斷是否滿足條件，直到找到答案。o（n＊n）的時間複雜度，在1e18這樣量級的數據，超時是肯定的，因此找 k 的方法也需要改進。

由上面的描述的可以發現在 m ＋k 天之前，麻雀沒有將 剩餘糧食吃完，而在 m＋k 天之後，肯定能將糧食吃完，並且，越往後，吃不到糧食的麻雀越多。得出的規律為：越靠近 m＋k 這一天，剩餘的糧食或者吃不到糧食的麻雀會越少。當然，題目要求只考慮 m ＋k 天及之前的情況，不考慮 m＋k 天之後，因此只需要考慮的特征就是 越靠近 m ＋k 這一天糧食剩餘數越少這一特征。

其次麻雀每天增長的數量有線性的關係，因此 如果 第 i 天麻雀沒吃完，那麼可以肯定 i 天之前，麻雀一定沒有將糧食吃完，那就不用判斷 i天之前的情況了。同樣，如果 第 i 天 麻雀已經將糧食吃完了，那麼在 i 天之後，麻雀一定能將糧食吃完，也不用考慮 i 天之後的情況。現在就需要每次找一個 測試的值 i ，將區間一分為二，在滿足條件的那一半尋找。那麼這個測試值取多少合適呢，經實踐發現，每次將區間等分查找的效率最高，

即 i 取 （左邊界＋右邊界）／2。這就是著名的 二分思想。時間複雜度是o（log n）的。

具體代碼實現有興趣的請打開網頁 http://paste.ubuntu.com/24268046/。