登录以参加训练计划

课件

二分答案概述

二分答案是一种通过二分搜索来求解"最大化最小值"或"最小化最大值"问题的算法技巧。

核心思想：将求解问题转化为判定问题，然后使用二分查找在答案的可能范围内寻找最优解。

二分答案解题步骤

1. 确定答案范围：找到答案的最小值和最大值
2. 编写check函数：判断某个答案是否可行
3. 二分搜索：在答案范围内进行二分查找
4. 输出最优解：找到满足条件的最大/最小值

典型应用场景

最大化最小值

• 砍树：最大化砍树高度
• 木材加工：最大化每段木材长度
• 跳石头：最大化最短跳跃距离

最小化最大值

• 数列分段：最小化每段和的最大值
• 路标设置：最小化相邻路标间最大距离

关键技巧

1. 确定答案范围

int left = 下界;  // 最小可能值
int right = 上界; // 最大可能值

2. check函数设计

bool check(int x) {
    // 判断以x为答案是否可行
    // 返回true表示可行，false表示不可行
}

3. 二分查找框架

while (left <= right) {
    int mid = (left + right) / 2;
    if (check(mid)) {
        // 可行，尝试更大/更小的答案
        left = mid + 1;  // 或 right = mid - 1;
    } else {
        // 不可行
        right = mid - 1; // 或 left = mid + 1;
    }
}

注意事项

1. 单调性：check函数必须具有单调性
2. 边界处理：注意答案的边界情况
3. 数据类型：使用足够大的数据类型（long long）
4. 循环条件：使用 while (left <= right) 确保不漏掉解