二分答案

二分答案

难点在于如何将最优化问题转变为判定问题（即针对具体的问题设计出合适的check函数是解决的关键）。求解一个问题很难，但是判断一个答案是不是问题的解相对简单。https://www.acwing.com/blog/content/91/

同济大学2020ICPC训练这里面讲的二分答案相对于网上一些关于二分答案的文章较为通俗易懂。

二分答案

二分答案与二分查找类似，即对有着单调性的答案进行二分，大多数情况下用于求解满足某种条件下的最大（小）值。

答案单调性

答案的单调性大多数情况下可以转化为一个函数，其单调性证明多种多样，如下：

移动石头的个数越多，答案越大（NOIP2015跳石头）。

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

满足更少分配要求比满足更多的要求更容易（NOIP2010关押罪犯）。

满足更大最大值比满足更小最大值的要求更容易（NOIP2015运输计划）。

时间越长，越容易满足条件（NOIP2012疫情控制）。

可以解决的问题

把求最优解的问题，转化为给定一个值 mid ，判定是否存在一个方案，达到 mid 的问题。(二分答案转化为判定)。

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

求最小的最大值（NOIP2010关押罪犯）。

求满足条件下的最小（大）值。

求最靠近一个值的值。

求最小的能满足条件的代价。

Leetcode LCP 12.小张刷题计划

核心代码块

Leetcode 410.分割数组的最大值

这一题和上一题大体相同，区别在于这次小张没有小杨的助攻。

Leetcode 1482.制作m束花所需的最少天数