二分枚举

二分重点：

1. 先判断什么具有二分性，再进行二分枚举
3. check：先从二分枚举的mid(答案)入手，倒推判断mid是否满足
2. 根据check的判断方式和逻辑来选择怎样二分，即用怎样的模板

1. AcWing 503. 借教室（每日一题）

• 暴力枚举：

  暴力挨个枚举 订单号(答案) 是O(n)复杂度，外加循环内check答案也是O(n)复杂度，总共O(n^2)，1e6的数据肯定超时了

• 二分枚举+差分优化：

  第一：订单号(答案)具有二分性：【 < k：左边订单号偏小全能借到教室，>= k：右边订单号偏大全不能借到教室 】
  第二：二分枚举订单号，从左往右找第一个不能借到教室的订单号——时间复杂度O(logn)
  第三：每个二分枚举的订单号check判断一下能否借到教室——时间复杂度O(n)

  注意：check需要差分数组优化才能达到O(n)

  总共时间复杂度为：O(nlogn)

• 点击展示代码

2. AcWing 1227. 分巧克力

• 暴力枚举：

  暴力枚举 边长(答案) 是O(n)复杂度，外加循环内check答案需枚举每一块巧克力也是O(n)复杂度,总共O(n^2)复杂度，1e5数据肯定会超时

• 二分枚举：

  第一：边长(答案)具有二分性：【 <= k：左边边长都能满足平均切完后块数够小孩分，> k：右边边长都不能满足平均切完后块数够分给小孩 】
  第二：二分枚举边长，从左往右找最后一个能满足平均切完后块数够小孩分的边长——时间复杂度O(logn)
  第三：check二分枚举的边长，判断能否满足平均切完后块数够小孩分——时间复杂度O(n)

  注意：注意二分模板的选取和边长与块数成反比

  总共时间复杂度：O(nlogn)

• 点击展示代码

3. AcWing 5407. 管道

• 暴力枚举：

  暴力枚举 秒数(答案) 肯定会狠狠地超时

• 二分枚举+区间合并：

  第一：秒数(答案)具有二分性：【 < k：左边秒数全未浸满，>= k：右边秒数全能浸满 】
  第二：二分枚举秒数，从左往右找第一个能浸满的秒数——时间复杂度O(logn)
  第三：check每个二分枚举的秒数，判断能否浸满——时间复杂度O(nlogn)

  check如下：
  1. 区间合并：将已经在流水的阀门在此秒数时刻浸水的长度转换为一个区间，对区间左边界排序后进行区间合并
  2. 判断：(能连续合并) 且 (合并完后区间为[1,len]) 则可以填满，反之则不能填满
  

  注意：

  1. 区间合并时，根据题意相隔一个单位也能合并，例如：[x,y]和[y+1,z]是可以合并的
  2. 二分范围很大，最大 秒数(答案) 可以为1999999999，容易爆int，**十年OI一场空，不开longlong见祖宗**
  

  总共时间复杂度：O(nlognlogn)

• 点击展示代码

4. AcWing 4956. 冶炼金属

• 暴力枚举：

  暴力枚举 转化率(答案) 肯定超时，无稽之谈

• 二分枚举：

  第一：转化率(答案)具有二分性：【 < k：左边转换率全偏小，= k：正确转化率值，> k：右边转化率全偏大 】
  第二：两次二分枚举转化率，分别找从左往右第一个满足的转化率（左边界）和最后一个满足的转化率（右边界）——时间复杂度O(logn)
  第三：check判断每个二分枚举的转化率是偏大还是偏小——时间复杂度O(n)

  注意一：

  1. 二分模板的选取与找左右边界有关
  

  注意二：

  2. 找左边界check判断时，有一个产品转化率偏小就认定为偏小，找右边界check判断时，有一个产品转化率偏大就认定为偏小
  

  总共时间复杂度：O(nlogn)

• 点击展示代码

5. AcWing 789. 数的范围

• 暴力枚举：

  略过......

• 二分枚举：

  第一：有序数列一定具有二分性：【 < k：左边偏小，= k：目标值，> k：右边偏大 】
  第二： 两次二分找目标值的左边界和右边界即可 时间复杂度O(logn)

  注意：

  1. 找目标值的左边界和右边界采用不同的二分模板
  

  总共时间复杂度：O(nlogn)

• 点击展示代码

6. AcWing 102. 最佳牛围栏

• 暴力枚举：

  暴力枚举区间——O(n^2)，循环内统计区间和O——(n),总共O(n^3),可以通过前缀和优化为O(n^2),仍然超时

• 二分枚举：

  第一： 均值的最大值（答案）均值有序一定能二分
  第二： 浮点数二分找的目标值——时间复杂度O(logn)

  注意：

  1. 线性映射：所有数减去mid,方便后续总和直接与0比较，不用总和除以统计个数求均值与mid比较
  2. 双指针枚举+前缀和+一个变量记忆最小前缀和的值
  达到O(n)时间复杂度统计满足的区间中的最大值
  

  总共时间复杂度：O(nlogn)

• 点击展示代码