二分答案

二分答案

什么是二分答案？

答： 二分答案就是通过对所有可能的答案区间进行折半查找，不断缩减范围，最终确定答案的方法。

典型的使用场景：

要求我们求出某种条件的最大值的最小可能情况或者最小值的最大情况

使用前提:

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

相比与二分查找，二分答案对答案进行折半枚举，概括一下二分答案的思想就是 guess and check 。

举个例子

1802. Maximum Value at a Given Index in a Bounded Array

题目描述

You are given three positive integers n, index and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:

• nums.length == n
• nums[i] is a positive integer where 0 <= i < n.
• abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.
• The sum of all the elements of nums does not exceed maxSum.
• nums[index] is maximized.

Return nums[index] of the constructed array.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Example 1:

Input: n = 4, index = 2,  maxSum = 6
Output: 2
Explanation: The arrays [1,1,2,1] and [1,2,2,1] satisfy all the conditions. There are no other valid arrays with a larger value at the given index.

Example 2:

Input: n = 6, index = 1,  maxSum = 10
Output: 3

Constraints:

• 1 <= n <= maxSum <= 109
• 0 <= index < n

思路

通过对 maximum value 进行枚举，并进行核验，最终确定答案。

核验计算时要注意判断剩余的数组长度与 maximum value = x 的关系：

• pattern 1 : 1, 1, 1, ..., x - 1, x, ...
• pattern 2 : x - y, ...., x - 2, x - 1, x, ....

代码

class Solution {
public:
    // auther : deardeer
    int maxValue(int n, int index, int maxSum) {
        // 2,3,2,1,1,1
        // 1, 1, 2, 1 
        // ..., x - 1, x, x - 1, ...
        if(maxSum == n) return 1;

        auto calc = [&] (int x, int len) -> long {
            long sum = 0;
            if(x <= len) {
               sum += len - x + 1LL * x * (1 + x) / 2; 
            }
            else sum += 1LL * len * (x + x - len + 1) / 2;
            return sum;
        };

        int l = 1, r = maxSum - n + 1;
        while(l <= r) {
            int x = l + (r - l) / 2;
            long sum = x + calc(x - 1, index) + calc(x - 1, n - 1 - index);
            if(sum > maxSum) r = x - 1;
            else l = x + 1;
        }
        return r;
    }
};

875. Koko Eating Bananas

题目描述

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

思路

这道题和上面的题目做法类似，区别是枚举答案检验的方法稍有区别。

对吃香蕉的速度进行枚举，再检验以速度 m 是否能在 h 小时吃完所有香蕉，值得一提的是，检查是否能做 h 小时吃完香蕉计算过程中 cnt += (pile + m - 1) / m 的写法。

代码

class Solution {
public:
    // auther : deardeer
    int minEatingSpeed(vector<int>& piles, int h) {
        auto judge = [&] (int m) {
            int cnt = 0;
            for(int p : piles) {
                cnt += (p + m - 1) / m; // + m - 1
                if(cnt > h) return false;
            }
            return true;
        };
        int l = 1, r = 1e9;
        while(l <= r) {
            int m = l + (r - l) / 2;
            auto check = judge(m);
            if(check) r = m - 1;
            else l = m + 1;
        }
        return l;
    }
};