以下摘要由GPT-4o生成:
本文讨论了序列二分的几种方法，包括暴力解法和二分优化。首先介绍了upper_bound和lower_bound函数的使用，前者用于找到序列中第一个严格大于x的位置，后者用于找到大于等于x的位置。接着，强调了核心代码的定制修改。此外，还提到了一些相关题目，如最小值最大问题和数列分段问题，同样适用于二分法的应用，特别是在处理具有单调性和二分性的场景中。

序列二分

0最大通过数 - 蓝桥云课

  • 暴力解法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    //暴力解法
    const int N = 200010; //2*10^5
    int n, m, k;
    LL a[N],b[N];
    int ans;
    int main() {
        cin >> n >> m >> k;
        for (int i  = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            a[i] = a[i - 1] + a[i];
        }
        for (int j = 1; j <= m; j++) {
            scanf("%lld", &b[j]);
            b[j] = b[j - 1] + b[j];
        }
        //求前缀和数组，进入到第i关所需要的能量为a[i];
        for (int i = 0; i <= n; i++) {
            LL temp = k - a[i];
            if (temp < 0) break;
            for (int j = 0; j <= m; j++) {
                if (temp < b[j]) {//找出第一个不能打的关卡
                ans = max(i + j - 1, ans);
                break;
                }
            }
        }
        cout << ans;


        return 0;
    }

  • 二分优化

  • upper_bound(a.begin(), a.end(), x) - a找出序列中第一个严格大于x的位置(与sort都为左闭右开区间)

  • *lower_bound 找出序列中大于等于x的位置,返回值为引用。

  • 手写上述两个序列二分

    1
    2
    3
    4
    5
    6
    7
    int l = 0; r = a.size() - 1;
    while (l < r) {
    	int mid = l + r + 1 >> 1;
    	if (a[mid] <= x) l = mid;
    	else r = mid - 1;
    }
    cout << l << "为大于x的位置,即upper_bound"
    1
    2
    3
    4
    5
    6
    7
    int l = 0; r = a.size() - 1;
    while (l < r) {
    	int mid = l + r >> 1;
    	if (a[mid] >= x) r = mid;
    	else l = mid + 1;
    }
    cout << l << "为大于等于x的位置,即lower_bound"

    **对于核心代码的修改 **

1
2
3
4
5
6
for (int i = 0; i <= n; i++) {
       LL temp = k - a[i];
       if (temp < 0) break;
       int j = upper_bound(b, b + m + 1, temp) - b - 1;
       ans = max(ans, j + i);
   }

答案二分

二分答案 - 题目详情 - HydroOJ最小值最大

  • 暴力解法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    //暴力解法
    const int N = 100010; //1*10^5
    int n, k;
    int a[N];
    int main() {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        for (int i = 1; i <= 1e14; i++) {//依次枚举这个最小值,ER
            LL x = k;//k次操作，随着i枚举值的最大，x成递减趋势。
            for (int j = 1; j <= n; j++) {
                if (a[j] < i) {//如果当前值有小于这个最小值的，那么可以进行增大这个数，进行操作，直到操作数小于0
                    x = x - (i - a[j]);//需要这个最小值i最大,x最小
                }
                if(x < 0) {
                    cout << i - 1;
                    break;
                } //减小到为0的时候，
            }
        }
        return 0;
    }

  • 核心代码二分优化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    //暴力解法
    const int N = 100010; //1*10^5
    LL n, k;
    int a[N];
    bool check(LL m) {
        LL x = k;//k次操作，随着i枚举值的最大，x成递减趋势。
        for (int j = 1; j <= n; j++) {
            if (a[j] < m) {
                x = x - (m - a[j]);//需要这个最小值i最大,x最小 
            }
            if(x < 0) {
                return false;
            } //减小到为0的时候，
        }
        return true;
    }
    int main() {
        scanf("%lld %lld", &n, &k);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        LL l = 1, r = 1e14;
        while (l < r) {
            LL mid = l + r + 1>> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
    cout << l;
        return 0;
    }

  • 最大值最小

P1182 数列分段 Section II - 洛谷

  • 暴力代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    for (int i = 1; i <= R; i++) {
        //R即为最大值的最大范围
        //即分一个段的时候，这个段的最大值,N个数，每个数为10^8,即N * 10^8
    	 int sum = 0, cnt = 1;
        for (int j = 1; j <= n; j++) {
            if (a[j] > mid) return;//终止条件。
            if (sum + a[j] <= mid) {
                sum += a[j];
            } else {
                sum = a[j];
                cnt ++;
            }
        }
    }

  • 二分优化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #include <iostream>
    #include <cstdio>
    using namespace std;
    int n, m;
    const int N = 1e5 + 10;
    int a[N];
    bool check(int mid) {
        int sum = 0, cnt = 1;
        for (int j = 1; j <= n; j++) {
            if (a[j] > mid) return false;
            if (sum + a[j] <= mid) {
                sum += a[j];
            } else {
                sum = a[j];
                cnt ++;
            }
        }
        return cnt <= m;//m是固定的段数，cnt是当前答案分的段数，说明分的ans太大，固定段数用不完
    }

    int main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        int l = 0, r = 1e9;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) {//如果当前值满足条件，那么mid后续值都满足条件，就缩小ans
                r = mid;
            }else l = mid + 1;
        }
        cout << l;
        return 0;
    }
    //此题的核心思想为：我们需要在给定数值个数，与分段数的情况下找出每个段里面的最大值，使得整个最大值最小
    //那么减小这个值的时候，分的段数就会增多，只需让段数cnt <= m即可继续减小，也就是让最大值 >= da'an

  • 寻找零界点，判断是否有二段性，是否满足单调性

  • 判断题型思考顺序:二分->dfs(暴搜)->动态规划->贪心

    730. 机器人跳跃问题 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
const int N = 100010;
int h[N];
int n;
bool check(int e) {
    
    for (int i = 0; i < n; i++) {
        e = 2 * e - h[i];//变化值
        if (e > 1e5) return true;//在增加过程中剪枝，防止爆掉int
        if (e < 0) return false;//不满足条件
    }
    return true;//变化过程中没有出现 e < 0情况，全部满足。
}

int main() {
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &h[i]);
    
    int l = 1, r = 1e5;//枚举开始能量携带值，如果初始值大于1e5，代表无论如何都满足e > h,都会递增。
    while (l < r) {
        int mid = l + r >> 1;
        //如果当前值e满足条件，那么往后的所有e都满足条件。
        if (check(mid)) r = mid;//有可能当前值就是答案。
        else l = mid + 1;
    }
    
    printf("%d", r);
    
    
    return 0;
}
//此题的核心思想为：初始值的能量大于某个值时候，后续能量会单调递增，相反，如果小于此值后续能量会单调递减，如果能量小于0，则不符合
//那么我们需要找出满足e > 0的最小的初始能量，随着初始值的不同，后续能量的变化也呈现出单调递增(递减)。

浮点数二分

0M次方根 - 蓝桥云课

  • 注意精度损失，一般相差100倍即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstdio>
using namespace std;
double esp = 1e-9;
int N, M;

bool check(double x) {
  double ans = 1;
  for(int i = 0; i < M; i++) {
    ans = ans * x;
  }
  return ans <= N;//乘出来结果小于N，即代表l = mid ,还可以继续增大
}

int main()
{
  cin >> N >> M;
  double l = 1, r = N;//最多为M为1的时候，r即N；
  while (l + esp < r) {
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
  }  
  printf("%0.7f", l);

  return 0;
}

总结

  • 二分法通常用来缩短找出序列中某个元素的时间

  • 在序列二分中，我们通常找出第一个严格大于x的值的位置，判断式为:a[mid] <= x即类似upper_bound函数

    或者找出大于等于x的值的位置，判断式为：a[mid] >= x，成立的话即满足当前式子的往后所有序列都大于等于x，前提是此序列是单调递增。

  • 在答案二分中我们借助这一特性来快速查找所要求的答案值，并且在枚举的过程中找出符合题干要求的值的可能范围，比如浮点数二分中，我们要找出满足x ^ m = n，在求出x可能值后代入判断式，如果得出判断式x ^ m = ans小于等于n，那么此时x前面的所有值带入判断式都会小于n，所以增大x,并且当前x有可能是答案值,所以l = mid，将左段点增大包含当前点。