知识点

整数二分

  1. bool check(int x) {/* ... */} // 检查x是否满足某种性质
  3. // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
  4. int bsearch_1(int l, int r)
  5. {
  6.     while (l < r)
  7.     {
  8.         int mid = l + r >> 1;
  9.         if (check(mid)) r = mid;    // check()判断mid是否满足性质
  10.         else l = mid + 1;
  11.     }
  12.     return l;
  13. }
  14. // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
  15. int bsearch_2(int l, int r)
  16. {
  17.     while (l < r)
  18.     {
  19.         int mid = l + r + 1 >> 1;
  20.         if (check(mid)) l = mid;
  21.         else r = mid - 1;
  22.     }
  23.     return l;
  24. }
  • 对于无解的处理

把最初的二分区间[1, n]扩大为1, n+1和0, n，包含一个越界下标，如果二分后终止于越界下标上，说明a中不存在要求的数

实数域二分

  1. bool check(double x) {/* ... */} // 检查x是否满足某种性质
  3. double bsearch_3(double l, double r)
  4. {
  5.     const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求，一般是题目要求的精度+2
  6.     while (r - l > eps)
  7.     {
  8.         double mid = (l + r) / 2;
  9.         if (check(mid)) r = mid;
  10.         else l = mid;
  11.     }
  12.     return l;
  14.     // 精度不容易确定时，直接循环固定次数，精度更高
  15.     for (int i = 0; i < 100; i++) {
  16.         double mid = (l + r) / 2;
  17.         if (calc(mid)) r = mid; else l = mid;
  18.     }
  19. }

三分求单峰函数极值

  • 单峰函数
    • 有唯一的极大值点：左侧严格单调上升，右侧严格单调下降
    • 极小值点类似
  • 在定义域[l, r]上任取两个点lmid和rmid，把函数分成三段
    • 若f(lmid) < f(rmid)，极大值点在lmid右侧，令l = lmid
    • 若f(lmid) > f(rmid)，极大值点在rmid左侧，令r = rmid
  • 如果取lmid和rmid为三等分点，那么定义域每次缩小1/3，取lmid, rmid在二等分点两侧极其接近的地方，那么定义域范围近似缩小1/2
  • 如果f(lmid) = f(rmid)，函数在两侧严格单调时，令l = lmid或者r = rmid均可，否则三分法不再适用

    二分答案转化为判定

    把求最优解的问题，转化为给定一个值mid，判定是否存在一个可行方案评分达到mid的问题
    典型情境是最大值最小

    例题

    整数二分

    特殊排序

    通过二分找到当前元素应该插入的位置，这就要求每插入一个元素后，当前序列都是有序的，很容易想到插入排序 ```cpp // Forward declaration of compare API. // bool compare(int a, int b); // return bool means whether a is less than b.

class Solution { public: vector specialSort(int N) { vector res; res.push_back(1);

  1.     for (int i = 2; i <= N; i++) {
  2.         int l = 0, r = res.size() - 1;
  3.         while (l < r) { // l = r = 小于i的最后一个元素的位置，也有可能不存在，此时为0
  4.             int mid = l + r + 1>> 1;
  5.             if (compare(res[mid], i)) l = mid;
  6.             else r = mid - 1;
  7.         }
  9.         res.push_back(i);
  10.         for (int j = res.size() - 2; j > r; j--) swap(res[j + 1], res[j]);
  11.         if (!compare(res[r], res[r + 1])) swap(res[r], res[r + 1]);
  12.     }
  14.     return res;
  15. }

};

  1. <a name="YDSJL"></a>
  2. ## 判定
  3. <a name="zrfVn"></a>
  4. ### [最佳牛围栏](https://www.acwing.com/problem/content/104/)
  5. 平均值的最大值，也是二分判定的典型场景<br />关键在于判断合法性：子段平均数不小于二分的值，长度不小于L<br />平均数的判定，可以将序列中的每个数减去这个平均值，这样最后子段和非负即可，也就是求最大子段和<br />长度不小于L，可以用前缀和+双指针的方式
  7. - 子段和转化成前缀和相减
  8. - 由于每次只有一个新元素i加入，只需要记录[0, i]区间内最小值，用sum[i]减去即可得到当前的最大值。一个指针从0开始，一个指针从长度L处开始
  9. ```cpp
  10. #include <iostream>
  12. using namespace std;
  14. const int N = 1e5 + 10;
  15. const double eps = 1e-5;
  17. int a[N];
  18. double s[N];
  19. int n, f;
  21. bool check(double avg) {
  22.     for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i] - avg;
  24.     double mins = 0;
  25.     for (int i = 0, j = f; j <= n; i++, j++) {
  26.         mins = min(mins, s[i]);
  27.         if (s[j] >= mins) return true;
  28.     }
  29.     return false;
  30. }
  32. int main() {
  33.     cin >> n >> f;
  35.     for (int i = 1; i <= n; i++) {
  36.         scanf("%d", &a[i]);
  37.     }
  39.     double l = 0, r = 2000;
  40.     while (r - l > eps) {
  41.         double mid = (l + r) / 2;
  42.         if (check(mid)) l = mid;
  43.         else r = mid;
  44.     }
  46.     cout << int(r * 1000);
  48.     return 0;
  49. }