Paresta's Blog

1
// 在vec中查找值等于num的数的下标
2
int binary_search(vector<int>& vec, int num) {
3
    if (vec.empty()) return -1; // 防止下一行溢出
4
    int left = 0, right = vec.size() - 1;
5
    while (left <= right) {
6
        int mid = left + (right - left) / 2;
7
        if (vec[mid] == num) {
8
            return mid;
9
        } else if (vec[mid] < num) {
10
            left = mid + 1;
11
        } else if (vec[mid] > num) {
12
            right = mid - 1;
13
        }
14
    }
15
    return -1;
16
}

1
// 在vec中查找最左侧的值等于num的数的下标
2
int search_left(vector<int>& vec, int num) {
3
    if (vec.empty()) return -1;
4
    int ans = -1;
5
    int left = 0, right = vec.size() - 1;
6
    while (left <= right) {
7
        int mid = left + (right - left) / 2;
8
        if (vec[mid] == num) {
9
            ans = mid;
10
            right = mid - 1;
11
        } else if (vec[mid] < num) {
12
            left = mid + 1;
13
       } else if (vec[mid] > num) {
14
            right = mid - 1;
15
        }
16
    }
17
    return ans;
18
}

1
if (vec[mid] > num) {
2
    ans = mid;
3
    right = mid - 1;
4
} else {
5
    left = mid + 1;
6
}

1
if (check(vec[mid])) {
2
    ans = mid;
3
    right = mid - 1;
4
} else {
5
    left = mid + 1;
6
}

1
// 在[L, R]区间内搜索符合check()的最小值
2
int search(int L, int R) {
3
    int ans = -1;
4
    int left = L, right = R;
5
    while (left <= right) {
6
        int mid = left + (right - left) / 2;
7
        if (check(mid)) {
8
            ans = mid;
9
            right = mid - 1;
10
        } else {
11
            left = mid + 1;
12
        }
13
    }
14
    return ans;
15
}

1
bool check(int limit, int m, vector<int>& A) { // 显然check函数除了limit还可以设置其它参数
2
    int count = 1;       // 当前需要的人数
3
    int current_sum = 0;
4

5
    for (int task_time : A) {
6
        if (current_sum + task_time <= limit) {
7
            current_sum += task_time;
8
        } else {
9
            ++count;
10
            current_sum = task_time;
11
            // 如果人数超过了限制，说明 limit 定小了
12
            if (count > m) return false;
13
        }
14
    }
15
    return true;
16
}

1
int search(int m, vector<int>& A) {
2
    // 单次遍历获取左边界max和右边界sum
3
    int max_task = 0;
4
    int sum = 0;
5
    for (int task_time : A) {
6
        if (task_time > max_task) max_task = task_time;
7
        sum += task_time;
8
    } // 实际题目中需注意输入数据范围
9

10
    int left = max_task, right = sum;
11
    int ans = -1;
12
    while (left <= right) {
13
        int mid = left + (right - left) / 2;
14
        if (check(mid, m, A)) {
15
            ans = mid;
16
            right = mid - 1;
17
        } else {
18
            left = mid + 1;
19
        }
20
    }
21
    return ans;
22
}

1
if (check(mid, m, A)) {
2
    ans = mid;
3
    left = mid + 1;
4
} else {
5
    right = mid - 1;
6
}

## 引入 **最大值最小化**问题, 是一类**选择一种合适的方案, 使得某个数据的最大值尽可能小**的问题. 比如: > (Leetcode 410) 给定一个非负整数数组 `nums` 和一个整数 `k` ，你需要将这个数组分成 `k` 个非空的连续子数组，使得这 `k` 个子数组各自和的最大值 **最小**。 意思是, 我们需要选择一种合适的分法, 使得所有子数组之和中, 最大的那一个子数组和**尽可能小**. 最大值变小了, 其它的子数组和也会相应变小, 以不超过新的最大值. 相当于将子数组和整体往小压缩. 因此, 下面的问法也是等价的: > (Leetcode 475) 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖, 在加热器的加热半径范围内的每个房屋都可以获得供暖。 > > 给出位于一条水平线上的房屋 `houses` 和供暖器 `heaters` 的位置，请你找出并返回可以覆盖所有房屋的**最小**加热半径。 问题中并没有**最大值**的字样. 但根据题意, 每台供暖器的加热半径是固定的, 我们不能漏掉任何一个房屋的供暖, 所以应当确定的是**半径的最大值**才能保证全覆盖. 然后, 我们想让这个最大值尽可能小, 因此这也是最大值最小化问题. 当然, 如果值太过小, 就无法全覆盖了. 因此左边界是有限制的. 同理, 我们也有**最小值最大化**问题, 含义是类似的. 在实际场景中, 最大值最小化往往是使成本或耗时尽可能减小, 而最小值最大化是使收益尽可能增大. 接下来我们逐步从基本的二分查找开始, 循序渐进得到该问题的解法. ## 从二分查找开始 我们默认读者了解基本的二分查找, 即*在一个有序数组中, 用$O(logN)$的时间复杂度查找某个数对应的下标*. 以下是一个基本的二分查找模板: ```cpp // 在vec中查找值等于num的数的下标 int binary_search(vector<int>& vec, int num) { if (vec.empty()) return -1; // 防止下一行溢出 int left = 0, right = vec.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (vec[mid] == num) { return mid; } else if (vec[mid] < num) { left = mid + 1; } else if (vec[mid] > num) { right = mid - 1; } } return -1; } ``` 接下来我们思考另一个问题: **在值可能不唯一的数组中, 如何查找相等值中最左边的那一个?** 首先, 我们通过原本算法搜索到的下标结果**不一定**表示最左边的值. 因此在搜索到结果后, 应当**进一步往左搜索**, 希望能找到更左的值. 我们用 `ans` 变量存储搜索到的值. 当 `vec[mid] == num` 时, 我们不直接 `return mid` , 而是存储 `ans = mid` , 然后令 `right = mid - 1` , 进一步向左搜索. 那么如何判断是否还有更左的值呢? 我们只需要在 `while (left <= right)` 的条件下**继续跑完整个二分流程**, 直到退出循环. 此时的 `ans` 就是最左值的下标. 因为: 1. 如果 `right = mid - 1` 后计算出新的mid依然位于 `num` 的位置, 就更新 `ans` , 继续向左搜索. 2. 如果发现新的 `mid` 跑的太远, 已经比最左边的 `num` 还要左了, 就通过原本的 `left = mid + 1;` 把它往右拉回来. 此外, 假如一个等于 `num` 的数都没有, 应当返回 `-1` , 因此我们令 `ans` 的初始值为 `-1` , 如果循环结束之前都没有更新过 `ans` , 就原样返回. 最终的代码如下: ```cpp // 在vec中查找最左侧的值等于num的数的下标 int search_left(vector<int>& vec, int num) { if (vec.empty()) return -1; int ans = -1; int left = 0, right = vec.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (vec[mid] == num) { ans = mid; right = mid - 1; } else if (vec[mid] < num) { left = mid + 1; } else if (vec[mid] > num) { right = mid - 1; } } return ans; } ``` 如果寻找**最右侧的下标**, 只需要在 `else` 分支改为 `left = mid + 1` 即可. ## 循序渐进 现在我们再进一步. 如果问的是**数组中第一个大于num的数**呢? 此时我们判断结果是否能存储到 `ans` 的条件就不是 `vec[mid] == num` 了, 只要 `vec[mid] > num` 就可以向左继续搜索. 这样判断分支只有两个: ```cpp if (vec[mid] > num) { ans = mid; right = mid - 1; } else { left = mid + 1; } ``` 在这里, **第一个大于num的数**就相当于我们之前找的**最左侧的值**. *此时其实就相当于C++ STL中 `upper_bound()` 的功能.* 如果判断逻辑更为复杂, 我们可以提取为`check()`**函数**, 形如: ```cpp if (check(vec[mid])) { ans = mid; right = mid - 1; } else { left = mid + 1; } ``` 这已经非常接近最大值最小化问题解法的终极形态了. 更进一步, 如果我们不是在一个数组中搜索, 而是直接**在某个范围内**找到符合条件的数的最小值呢? 我们只需要从用数组的下标来搜索改为直接用数来进行搜索: ```cpp // 在[L, R]区间内搜索符合check()的最小值 int search(int L, int R) { int ans = -1; int left = L, right = R; while (left <= right) { int mid = left + (right - left) / 2; if (check(mid)) { ans = mid; right = mid - 1; } else { left = mid + 1; } } return ans; } ``` 非常好! 事实上, 现在我们的代码已经是一个**最大值最小化**的模板了. ## 核心 为什么这就是最大值最小化问题了? 因为在文章开头, 我们定义这是一类**选择一种合适的方案, 使得某个数据的最大值尽可能小**的问题. 而现在: 1. 通过不断二分搜索, 我们不断逼近最小的值 2. 通过 `check()` , 我们能判断一个值是仍在合理区间内, 还是已经突破下限不合题意了(如供暖半径无法全覆盖). 因此我们实际上已经进入到了最大值最小化问题的领域内. ### 单调性 之所以查找**第一个大于num的数**的逻辑可以直接用于这类问题, 是因为他们的问题都具有一个关键性质: **单调性**. 也就是说: - 如果某个值 `m` 是可行的, 那么大于 `m` 的值一定也是可行的. - 如果某个值 `n` 是不可行的, 那么小于 `n` 的值也一定是不可行的. 比如如果一个数50大于所需的 `num` 20, 那么比50大的数一定也大于20; 如果一个供暖半径3无法覆盖所有房屋, 更小的半径2一定更无法覆盖. 用 `check()` 来说, 就是 - 如果存在 `m` , 使得 `check(m) == true` , 那么对于所有 `x > m` , 有 `check(x) == true` - 如果存在 `n` , 使得 `check(n) == false` , 那么对于所有 `y < n` , 有 `check(y) == false` ### 解法 二分搜索部分的思路都是大致相同的, 此类问题的关键在于如何编写 `check()` 函数. 一般的方法是**贪心**或**动态规划**. 用一个实际的例子说明: > 有 $n$ 个任务, 时长分别为 $A = \{a_1, a_2, \dots, a_n\}$, 分配给 $m$ 个人, 如何总时长最多的那个人的总时长尽可能小? > > 规定任务是**连续分配**的, 不会出现同一个人完成$a_1, a_3$的情况 我们需要使总时长的最大值最小化. 为此, 我们应当对范围内所有的**总时长最大值** `limit` 进行搜索. 对于每个 `limit` , 判断其是否合理, 即判断 `check(limit)` 是否为 `true` . 我们需要找到一种判断的方法. 考虑如下的贪心算法: - 对于一个 `limit` , 遍历 `A` (存放每个任务时长的数组)中的每个 `task_time` . - 把 `task_time` 累加起来, 直到超出 `limit` , 此时说明某个人的总时长到极限了, 必须换下一个人分配任务. 将人数计数器 `count += 1` . - 如果所有 `task_time` 遍历完(分配完任务), `count` 未超过人数总数 `m` , 说明可行, 返回 `true` . 如果任何时候发现 `count > m` , 说明 `limit` 太小了, 就返回 `false` . 代码如下: ```cpp bool check(int limit, int m, vector<int>& A) { // 显然check函数除了limit还可以设置其它参数 int count = 1; // 当前需要的人数 int current_sum = 0; for (int task_time : A) { if (current_sum + task_time <= limit) { current_sum += task_time; } else { ++count; current_sum = task_time; // 如果人数超过了限制，说明 limit 定小了 if (count > m) return false; } } return true; } ``` 最难的一步完成了. 接下来是二分搜索的部分. 我们需要确定**搜索的范围**. - **左边界 `L`**: `limit` 最小的可能性. 至少要等于时间最长的那个任务, 即$L = \max(A)$. 比如 `A = [5, 1, 1, 1]` 时, 至少也需要 `limit = 5` . - **右边界 `R`**: 最坏的情况, 所有任务都分给一个人做, 即$R = \sum A$. 如果边界判断不准, 可以设置的**稍微大一些**, 也能得到正确的结果. 甚至即使设置为能涵盖整个样例输入的范围, 也不会对性能产生太大影响(毕竟是$O(logN)$). 得到搜索代码如下: ```cpp int search(int m, vector<int>& A) { // 单次遍历获取左边界max和右边界sum int max_task = 0; int sum = 0; for (int task_time : A) { if (task_time > max_task) max_task = task_time; sum += task_time; } // 实际题目中需注意输入数据范围 int left = max_task, right = sum; int ans = -1; while (left <= right) { int mid = left + (right - left) / 2; if (check(mid, m, A)) { ans = mid; right = mid - 1; } else { left = mid + 1; } } return ans; } ``` 另外, 由于本题**始终有解**, 令 `limit = R` 时一定是可行的, 因此不存在返回 `ans = -1` 的情况, 可以初始化 `int ans = right` . 进一步地, 在当前这种写法下, `ans` 的最终值必然等于 `left` , 因此可以不设置 `ans` 变量, 直接返回 `left` . 但是, 如果题目不一定有解, 则需要 `ans = -1` 来判断. 因此当前写法更为通用和清晰. 如果是**最小值最大化**问题, 只需要反转 `search()` 中的移动逻辑: ```cpp if (check(mid, m, A)) { ans = mid; left = mid + 1; } else { right = mid - 1; } ``` ## 总结 最大值最小化问题或最小值最大化问题可以归纳为三步: 1. **写 `check()`**. 方法根据题目而定, 各显神通awa 2. **定边界**. 宁可大不可小. 3. **套模板**. 默写二分查找代码. 开头的两道Leetcode题目可作为练习.