「二分法+贪心思想」的应用

发表于 2022-04-02 更新于 2023-01-04 Artalk： loading...

二分法贪心

应用二分法，结合贪心思想的例题

Ex:狒狒吃香蕉、分享巧克力

剑指 Offer II 073. 狒狒吃香蕉

题目描述

狒狒喜欢吃香蕉。现在有 $n$ 堆香蕉，每堆的香蕉数量为 $piles[i]$

狒狒需要在 $h$ 小时内吃完，每小时会选择一堆，吃掉 $k$ 根，本题目标是求最小进食速度 $k$ ，单位：根/小时

ps：如果一堆香蕉少于 $k$ 根，狒狒会一次吃掉这堆所有的香蕉。

示例：

1 2	输入: piles = [3,6,7,11], H = 8 输出: 4

思路

如何应用二分法？或者说，什么属性具备二段性？

本题中，狒狒每次最多选择一堆香蕉(不能一次吃两堆)，因此最大的进食速度 $k_{max} = max\{piles[i]\}$

最小进食速度理论上可以是 $1$

那么，针对一个给定的时限 $h$ ，存在一个进食速度 $k$

大于 $k$ 的进食速度一定能在时限内吃完所有的香蕉
小于 $k$ 的速度则一定无法在规定时间内吃完

进食速度 $k$ 具有两段性。

代码

对于当前的进食速度 $mid$ ，如果能吃完(吃完花费的时间小于限制 $h$ )，则向左侧收缩(减小方向)搜索区间，否则向右侧收缩。

public boolean check(int[] pils, int curSpeed, int h) {
    int time = 0;
    for (int x : pils) {
        time += (x + curSpeed - 1) / curSpeed;
    }
    return time <= h; // 判断总时间是否小于限制
}

当前“堆”的香蕉数量除以当前进食速度，取上界，即为吃完当前“堆”香蕉花费的时间。

完整代码：

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int n = piles.length;
        int max = 0;
        for (int x : piles) {
            max = Math.max(max, x);
        }
        int l = 1, r = max;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(piles, mid, h)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    public boolean check(int[] ps, int t, int h) {
        int time = 0;
        for (int x : ps) {
            time += (x + t - 1) / t;
        }
        return time <= h;
    }
}

1011. 在 D 天内送达包裹的能力

题目描述

ps：本题与上一题有所不同，一天可以运送多个包裹。而一个包裹不能拆分多次运送。

思路

重点还是找，哪种属性具备二段性？

本题很显然，是每天的运载能力，单位：重量/天

考虑最小的运载能力，至少也要保证一天运一个包裹，因此 $K_{min} = max\{weights[i]\}$

最大运载能力，则是一天就运完所有的包裹，即 $K_{max} = sum\{weights[i]\}$

其余同理。

代码

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int n = weights.length;
        int sum = 0;
        int max = 0;
        for (int i = 0; i < n; ++i) {
            max = Math.max(max, weights[i]);
            sum += weights[i];
        }
        int l = max, r = sum;
        while (l < r) {
            int mid = l + r >> 1; //
            if (check(weights, mid, days)) r = mid;
            else l = mid + 1;
        }
        return l;   
    }

    public boolean check(int[] ws, int t, int days) {
        int len = ws.length;
        int sum = ws[0];
        int cnt = 0; // 统计天数
        for (int i = 1; i < len; sum = 0, ++cnt) {
            while (i < len && sum + ws[i] <= t) {
                sum += ws[i];
                i++;
            }
        }
        return cnt <= days; // 小于规定时限则认为可以成功运送
    }
}

410. 分割数组的最大值

题目描述

思路

本题仔细分析就会发现，跟1011思路一模一样

由于数据范围为

1 \le nums.legth \le10^3,0\le nums[i]\le 10^6

可以使用模糊边界，初值设定， $left = 0, r=10^3\times10^6=10^9$ 二分法缩小搜索区间的效率是 $\log_2{n}$ 的，相比之下还减少了一次对数组的遍历。

代码

下面给出模糊边界的写法

class Solution {
    public int splitArray(int[] nums, int m) {
    
        int l = 0, r = (int) 1e9;

        while (l < r) {
            int mid = l + r >> 1;
            if (check(nums, mid, m)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    boolean check(int[] q, int tmp, int m) {
        if (q[0] > tmp) return false;
        int cnt = 0;
        int n = q.length;
        for (int i = 1, sum = q[0]; i < n; sum = 0, ++cnt) {
            if (q[i] > tmp) return false;
            while (i < n && sum + q[i] <= tmp) {
                sum += q[i];
                i++;
            }
        }
        return cnt <= m;
    }
}

1231. 分享巧克力

题目描述

解题思路

前言

之前求的都是

“最小的，数组和最大值”

“最小的，运载能力(每日运送货物的最大重量)”

本题是求，切分巧克力“最大的，最小甜度”

诸如此类问题，其实解决思路都是贪心的思想，并且可以使用二分法来优化。

实际上，不用二分，如果模糊边界，很可能会超时

~~本题逻辑与之前恰好相反，在细节上有所不同~~

问题

保证在每种分配方案，自己拿最小甜度的前提下，求在所有的分配方案中，自己能获得的最大甜度。

思路

“贪心”

保证其他所有人分得的甜度只比自己多一点，这样得到的一定是最优解

// 代码具体如何体现贪心
for (int i = 0; i < n; ++i) {
    sum += q[i];
    if (sum >= curSweetness) {
        sum = 0; // 一旦当前的分块”首次 大于“最小甜度，就作为一次符合策略的合法切分
        cnt++; // 然后开始切下一个分块
    }
}

最小甜度具有二段性，对于给定的切割块数 $N=K+1$ ，存在一个最优的最小甜度 $mid$

当最小甜度小于 $mid$ 时，巧克力能切分出的块数一定大于 $N$ ，方案可行
当最小甜度大于 $mid$ 时，巧克力能切分出的块数一定小于 $N$ ，此方案一定非法

因此可以针对“最小甜度”这个属性进行二分搜索

如果当前最小甜度curSweetness(mid)是合法的，则尝试增大最小甜度，向右收缩搜索区间
否则，继续减少最小甜度，向左收缩搜索区间

while (left < right) {
    int mid = left + right + 1 >> 1;
    if (check(sweetness, mid, k + 1)) { // 注意 切k刀，会分成k+1块
        left = mid;
    }
    else right = mid - 1;
}

完整代码

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        // 
        int l = 0, r = (int) 1e9;
        int ans = 0;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(sweetness, mid, k + 1)) {
                l = mid;
            }
            else r = mid - 1;
        }
        return l;
    }
    boolean check(int[] q, int curSweetness, int m) {
        int cnt = 0;
        int n = q.length;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += q[i];
            if (sum >= curSweetness) {
                sum = 0;
                cnt++;
            }
        }
        return cnt >= m;
    }
}

其他类似例题

5219. 每个小孩最多能分到多少糖果

题解

题目描述

代码

class Solution {
    public int maximumCandies(int[] candies, long k) {
        int n = candies.length;
        int max = 0;
        for (int i = 0; i < n; ++i) {
            max = Math.max(max, candies[i]);
        }
        int l = 0, r = max;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(candies, mid, k)) l = mid;
            else r = mid - 1;
        }
        return r;
    }
    // 对可以分到的最大糖果数量进行二分搜索
    boolean check(int[] q, int cur, long k) {
        int n = q.length;
        long cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt += q[i] / cur;
        }
        return cnt >= k;
    }
}

1891. 割绳子

题解

题目描述

代码

class Solution {
    public int maxLength(int[] ribbons, int k) {
        int l = 0, r = (int) 1e5;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(ribbons, mid, k)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

    boolean check(int[] q, int cur, int k) {
        int n = q.length;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt += q[i] / cur;
        }
        return cnt >= k;
    }
}

1760. 袋子里最少数目的球

题解

题目描述

代码

class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        // 二分 + 贪心
        int l = 1, r = (int)1e9;
        int ans = 0;
        // 贪心的思路，尽可能平均分，开销最小（最优）
        while (l < r) {
            int mid = l + ((r - l) >> 1); //
            if (check(nums, mid, maxOperations)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    boolean check(int[] nums, int cur, int maxOperations) {
        int cnt = 0;
        for (int num : nums) {
            cnt += (num + cur - 1) / cur - 1;
        }
        if (cnt <= maxOperations) return true;
        return false;
    }
}

1802. 有界数组中指定下标处的最大值

题解

题目描述

示例

1
2
3

输入：n = 4, index = 2,  maxSum = 6
输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组

分析

如果nums[index]相邻的数字都逐渐减少1，则总的和最小，也就能得到最大的nums[index]，此为最优思路（贪心）

记最大化的nums[index]为x，x具备单调性，可以二分搜索最大的合法x

PS：

x的单调性体现在，存在一个x

对于所有的nums[index] > x，按照最优思路构建的数组总和一定会大于maxSum
而当nums[index] < x时，构建的数组总和一定会小于maxSum

代码

class Solution {
    public int maxValue(int n, int idx, int maxSum) {
        // x-1, x, x-1, x-2, x-3, x-4;
        // idx
        // k = n - idx - 1
        // 二分查找 x 
        int l = 1, r = (int)1e9;
        while (l < r) {
            int mid = l + ((r - l + 1) >> 1);
            if (check(idx, mid, n, maxSum)) l = mid;
            else r = mid - 1;
        }
        return l;

    }

    boolean check(int idx, int x, int n, int maxSum) {
        // 分两种情况
        // case1: x >= idx + 1
        // 例如 ：2 3 4 [5] 4 3 2
        // case2: x < idx + 1
        // 例如 ：1 1 2 [3] 2 1 1 由于元素均为正整数(>= 1)，因此减少到1后不能继续减少
        // 此时，以左侧为例，所求为1到x-1的总和，再加上1的个数
        long left = x - idx >= 1 ? (long)(x - 1 + x - idx) * idx / 2 : (long)(x - 1) * x / 2 + (idx + 1 - x);
        int k = n - idx - 1;
        long right = x - k >= 1 ? (long)(x - 1 + x - k) * k / 2 : (long)(x - 1) * x / 2 + (k + 1 - x);
        return left + right + x <= maxSum;
    }
}