二分答案

難點在于如何將最優(yōu)化問題轉(zhuǎn)變?yōu)榕卸▎栴}（即針對具體的問題設(shè)計出合適的check函數(shù)是解決的關(guān)鍵）。求解一個問題很難，但是判斷一個答案是不是問題的解相對簡單。https://www.acwing.com/blog/content/91/

同濟大學(xué)2020ICPC訓(xùn)練這里面講的二分答案相對于網(wǎng)上一些關(guān)于二分答案的文章較為通俗易懂。

二分答案

二分答案與二分查找類似，即對有著單調(diào)性的答案進行二分，大多數(shù)情況下用于求解滿足某種條件下的最大（?。┲怠?/p>

答案單調(diào)性

答案的單調(diào)性大多數(shù)情況下可以轉(zhuǎn)化為一個函數(shù)，其單調(diào)性證明多種多樣，如下：

移動石頭的個數(shù)越多，答案越大（NOIP2015跳石頭）。

前i天的條件一定比前 i + 1 天條件更容易（NOIP2012借教室）。

滿足更少分配要求比滿足更多的要求更容易（NOIP2010關(guān)押罪犯）。

滿足更大最大值比滿足更小最大值的要求更容易（NOIP2015運輸計劃）。

時間越長，越容易滿足條件（NOIP2012疫情控制）。

可以解決的問題

把求最優(yōu)解的問題，轉(zhuǎn)化為給定一個值 mid ，判定是否存在一個方案，達到 mid 的問題。(二分答案轉(zhuǎn)化為判定)。

求最大的最小值（NOIP2015跳石頭）。

求最小的最大值（NOIP2010關(guān)押罪犯）。

求滿足條件下的最?。ù螅┲怠?/p>

求最靠近一個值的值。

求最小的能滿足條件的代價。

Leetcode LCP 12.小張刷題計劃

核心代碼塊

Leetcode 410.分割數(shù)組的最大值

這一題和上一題大體相同，區(qū)別在于這次小張沒有小楊的助攻。

Leetcode 1482.制作m束花所需的最少天數(shù)