一、课上练习

编程练习

1. 数列分段：L3141
2. 伐木工：L3142

二、知识总结

✨ 核心思想

二分答案（Binary Search the Answer）是二分查找算法的一种扩展应用，用于解决优化问题，特别是在问题的可能答案可以按序排列且可以进行"是或否"判定的情况下。这种技术通常用于在一个连续或离散的有序空间中寻找最优解。

二分答案技术的核心在于使用二分查找思想，通过对答案的范围进行不断缩小，快速逼近目标解。这种方法要求问题的解空间具有单调性，即解的有效性是单调的（非递增或非递减），从而可以明确地决定搜索范围的缩小方向。

✨ 算法原理

二分答案的具体执行步骤如下：

1. 确定范围：首先确定答案可能存在的最小值 low 和最大值 high。范围的确定需要根据题意分析，通常 low 取问题允许的最小值，high 取问题允许的最大值。
2. 中间值判断：计算中间值 mid = (low + high) / 2，然后通过一个判定函数检验 mid 是否为可行解。判定函数是二分答案的关键，它需要在 O(n) 或更优的时间内完成判断。
3. 调整范围：
   • 如果 mid 是一个可行解，则根据问题的需要（求最小值还是最大值），调整 low 或 high：
   • 如果我们需要最小的可行解，且 mid 可行，那么就将 high 调整为 mid
   • 如果我们需要最大的可行解，且 mid 可行，那么就将 low 调整为 mid + 1
   • 如果 mid 不可行，则相反地调整 low 或 high
4. 重复过程：重复上述过程，直到 low 和 high 的区间缩小到满足条件的程度（通常是 low 和 high 相遇）。

✨ 应用场景

二分答案常见的应用场景包括：

• 容量最小化问题：例如，确定最小的船只容量，使得所有货物都可以在限定次数内运送完毕
• 速度最大化问题：寻找最大速度，使得在这个速度或更低的速度下，完成某项任务的时间仍然可以接受
• 经济/成本问题：找到最少的投资额，使得可以获得预期的利润或效果

这些问题的共同特点是：答案越大（或越小），条件越容易（或越难）满足，具有明显的单调性。

✨ 代码实现

以下是一个利用二分答案技术解决查找问题的示例，展示了查找第一个和最后一个等于目标值的位置：

1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int findFirst(const vector<int>& nums, int target) {
7    int low = 0, high = nums.size() - 1;
8    int first = -1;
9    while (low <= high) {
10        int mid = low + (high - low) / 2;
11        if (nums[mid] >= target) {
12            if (nums[mid] == target) first = mid;
13            high = mid - 1;
14        } else {
15            low = mid + 1;
16        }
17    }
18    return first;
19}
20
21int findLast(const vector<int>& nums, int target) {
22    int low = 0, high = nums.size() - 1;
23    int last = -1;
24    while (low <= high) {
25        int mid = low + (high - low) / 2;
26        if (nums[mid] <= target) {
27            if (nums[mid] == target) last = mid;
28            low = mid + 1;
29        } else {
30            high = mid - 1;
31        }
32    }
33    return last;
34}
35
36int main() {
37    vector<int> nums = {1, 2, 4, 4, 4, 5, 6};
38    int target = 4;
39    cout << "First Position: " << findFirst(nums, target) << endl;
40    cout << "Last Position: " << findLast(nums, target) << endl;
41    return 0;
42}

✨ 执行示例

以经典的"伐木工"问题为例：有 n 棵树，高度分别为 h1, h2, ..., hn。伐木工设定一个锯片高度 H，所有高于 H 的树会被锯掉高于 H 的部分。求满足"获得至少 M 米木材"的最大 H。

样例数据：4 棵树高度为 [20, 15, 10, 17]，需要至少 7 米木材。

分析单调性：H 越低，获得的木材越多；H 越高，获得的木材越少。所以我们要找最大的 H 使得木材量 >= 7。

判定函数：给定 H，木材量 = sum(max(0, hi - H))

二分过程：low=0, high=20（最高的树）

最终答案：H = 15，此时恰好获得 7 米木材。

✨ 解题步骤详解

遇到二分答案问题时，按以下步骤分析：

1. 识别问题类型：如果题目要求"最大化某个值使得条件满足"或"最小化某个值使得条件满足"，很可能是二分答案。
2. 验证单调性：确认答案越大（或越小），条件越容易（或越难）满足。只有具备单调性，二分才有效。
3. 确定二分范围：分析答案的最小值和最大值。通常从题目的数据范围中可以推导出来。
4. 编写判定函数：这是最关键的一步。给定一个候选答案 mid，在 O(n) 时间内判断它是否可行。
5. 确定二分方向：
   • 求最大的可行值：mid 可行时 low = mid + 1，不可行时 high = mid - 1，答案记录在可行时。
   • 求最小的可行值：mid 可行时 high = mid - 1，不可行时 low = mid + 1，答案记录在可行时。
6. 注意整数/浮点：如果答案是整数，用标准整数二分。如果答案是浮点数，循环条件改为 high - low > 1e-6（精度要求）。

✨ 常见错误

• 单调性判断错误：如果问题不具备单调性，二分答案就不适用。使用前必须确认"答案增大时条件的满足情况单调变化"。
• 二分范围设置过小：如果 high 设得不够大，可能把正确答案排除在外。建议范围设得宽一些。
• 判定函数写错：判定函数的正确性直接决定了最终答案。建议单独测试判定函数，确保对边界情况也能正确判断。
• 求最大值和求最小值的逻辑混淆：这是二分答案最容易出错的地方。求最大可行值时，可行应该让 low 右移；求最小可行值时，可行应该让 high 左移。
• 整数二分的死循环：当 low + 1 == high 时，mid = (low + high) / 2 = low，如果此时 low = mid（而非 low = mid + 1），就会陷入死循环。

三、课后练习

编程练习

1. 愤怒的奶牛 USACO：L3143