二分答案法算法解析

使用场景

解决最小化最大值或最大化最小值类问题。
适用于具有单调性的优化问题。这种方法利用了答案的单调性，即如果某个值是可行解，那么比它更小的值（在最大化最小值的场景下）或者比它更大的值（在最小化最大值的场景下）也可能是可行的，这种单调性使得我们可以通过二分查找来高效地缩小答案的范围，从而找到最优解。

使用前提:

1. 答案在一个固定的区间内
2. 难以通过搜索来找到符合要求的值, 但给定一个值你可以很快的判断它是不是符合要求 –> 能够写出可行性判定函数
3. 可行解对于区间要符合单调性, 因为有序才能二分

本质就是因为答案一定在一个区间内，枚举所有可能的答案，正确的答案可能有多个，判断每一个答案是否正确，再取出答案中的最值，因为答案的可能值有序，所以用二分来进行优化(枚举 + 二分)

具体步骤

1. 确定二分范围：
   • 通常需要确定可能的解的最小值和最大值，设为 left 和 right。
2. 二分搜索：
   • 取中间值 mid = (left + right) / 2。
   • 使用一个可行性判断函数检查是否能够满足目标（即判断 mid 是否是一个可行解）。
3. 更新搜索范围：
   • 如果 mid 是可行的，尝试找到更优的解（例如，right = mid - 1）。
   • 如果 mid 不可行，尝试更大的范围（例如，left = mid + 1）。
4. 最终结果：
   • 当搜索范围收敛时，得到的就是最优解。

举例1

问题描述：分割数组使得最大和最小化

给定一个整数数组 nums 和一个整数 m，将数组分割成 m 段，使得每段的和尽量小。求最小可能的最大段和。

示例

输入: nums = [7, 2, 5, 10, 8], m = 2
输出: 18
解释:
将数组分割成 [7, 2, 5] 和 [10, 8]，它们的和分别是 14 和 18，最大和是 18。

思路

1. 确定二分范围：
   • 最小值：数组中单个元素的最大值，因为最优的划分不会使任何子数组小于数组中最大的元素。
   • 最大值：整个数组的和，因为最差的情况下就是将整个数组作为一个子数组。

   所以，left = max(nums)，right = sum(nums)。

2. 二分查找答案：
   • 我们在范围 [left, right] 中查找一个可能的最优值。
   • 每次取 mid，用可行性检查函数判断，如果以 mid 为最大和能否将数组分成 m 段或更少。
3. 可行性判断函数：
   • 遍历数组，模拟划分过程，统计当前的子数组和。
   • 如果子数组的和超过了 mid，则需要新开一个子数组。
   • 如果子数组个数超过了 m，说明 mid 过小。

C++ 实现

#include <iostream>
#include <vector>
#include <numeric> // for accumulate
#include <algorithm> // for max

using namespace std;

bool canSplit(vector<int>& nums, int m, int maxSum) {
    int currentSum = 0;
    int splits = 1; // 初始时有一个子数组
    for (int num : nums) {
        if (currentSum + num > maxSum) {
            // 如果当前子数组和加上 num 超过了 maxSum，开始新的一段
            splits++;
            currentSum = num;
            if (splits > m) {
                return false; // 无法在 m 段内实现
            }
        } else {
            currentSum += num;
        }
    }
    return true; // 可以用不超过 m 段来实现
}

int splitArray(vector<int>& nums, int m) {
    int left = *max_element(nums.begin(), nums.end());
    int right = accumulate(nums.begin(), nums.end(), 0);
    int result = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canSplit(nums, m, mid)) {
            result = mid; // mid 是可行的，尝试找到更小的可能解
            right = mid - 1;
        } else {
            left = mid + 1; // mid 不可行，尝试更大的值
        }
    }

    return result;
}

int main() {
    vector<int> nums = {7, 2, 5, 10, 8};
    int m = 2;
    cout << "The minimum possible largest sum is: " << splitArray(nums, m) << endl;
    return 0;
}

详细解释

1. 初始化二分边界：
   • left = max(nums)：因为最小的最大和至少要大于等于数组中的最大元素。
   • right = sum(nums)：所有元素加起来是可能的最大和。
2. 二分答案：
   • 计算 mid = (left + right) / 2。
   • 调用 canSplit() 函数，判断以 mid 为最大子数组和时，能否将数组分割成 m 段或更少。
   • 如果可以实现，说明当前 mid 是可行的，尝试更小的 mid 来找到更优解，因此 right = mid - 1。
   • 如果不可以实现，说明当前 mid 太小了，无法满足分成 m 段的要求，增大 mid，即 left = mid + 1。
3. 贪心验证 (canSplit 函数)：
   • 通过遍历数组，将元素加到 currentSum 中。
   • 如果 currentSum + num 超过了 maxSum，则新开一个子数组，并统计分割次数。
   • 如果分割次数超过了 m，则当前的 maxSum 太小。
4. 结果：
   • 最后 left 和 right 收敛到某个值，这个值就是最小的可能的最大和。

二分答案法的应用场景

• 最大化最小值：如分配工作、最大化最小分数。
• 最小化最大值：如本题分割数组、尽量平衡多个分段的大小。
• 具有单调性的问题：如果问题的解具有单调性，通常可以考虑使用二分答案法。