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

在这里插入图片描述

提示：

$1 <= days <= weights.length <= 5 * 10^4$
$1 < = w e i g h t s [i] < = 500$

一开始误以为是“背包问题”，后来看了三叶姐题解才发现原来是 “二分”。

二分

本题和 LeetCode-2226. 每个小孩最多能分到多少糖果有很大的相似之处。

思路 🤔

船所需的最低运载能力：为 max，即最起码能保证一次能把 $w e i g h t s$ 中最大的货物运输到另一港口；
船所需的最高运载能力：为 sum，即一次就把全部货物运输到另一港口；
开始二分

利用“两段性”：设最终所需最小装载能力 res。若运载能力 < res 时，则无法满足 $d a y s$ 天运输完所有货物；若运载能力 >= res 时，则可以满足 $d a y s$ 天运输完所有货物
- 当按照运载能力mid装船时，可以将所有货物都能在 $d a y s$ 天内都运输完毕，则“尝试”更小的装载量是否可以满足，即 right = mid - 1；
- 否则，则说明当前 mid 运载能力不足，则需要船具有更大的运载能力，即 left = mid + 1


class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int max = 0;
        int sum = 0;
        for (int weight : weights) {
            max = Math.max(max, weight);
            sum += weight;
        }
        int left = max;  // 最小运载能力
        int right = sum; // 最大运载能力
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(weights, mid, days)) { // 按照mid装船时，可以满足，则“尝试”更小的装载量是否可以满足，即mid - 1
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // 将weight
    boolean check(int[] weights, int target, int days) {
        int cnt = 0;
        for (int i = 0; i < weights.length; ) {
            int sum = 0;
            // 找一堆连续“最接近”（但不超过）target的总和
            while (i < weights.length && sum + weights[i] <= target) {
                sum += weights[i++];
            }
            cnt++;
        }
        return cnt <= days;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9,10};
        int days = 5;
        System.out.println(new Solution().shipWithinDays(nums, days));
    }
}

在这里插入图片描述

410. 分割数组的最大值

在这里插入图片描述

二分

本题和 1011. 在 D 天内送达包裹的能力基本一致

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int max = 0;
        int sum = 0;
        for (int i : nums) {
            sum += i;
            max = Math.max(max, i);
        }
        int left = max;
        int right = sum;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(nums, mid, m)) { // 尝试更小的“分堆和”
                right = mid - 1;
            } else {    
                left = mid + 1;
            }
        }
        return left;
    }

    boolean check(int[] nums, int target, int m) {
        int cnt = 0;
        for (int i = 0; i < nums.length; ) {
            int sum = 0;
            while (i < nums.length && sum + nums[i] <= target) {
                sum += nums[i++];
            }
            cnt++; // 增加“堆数”
        }
        return cnt <= m;
    }
}