1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public int shipWithinDays(int[] weights, int days) {
            int left = 0;
            int sum = 0;
            for (int weight : weights) {
                left = Math.max(left, weight);
                sum += weight;
            }
            int right = sum;

            while (left < right) {
                int mid = left + ((right - left) >> 1);

                if (f(weights, mid) <= days) {
                    // 满足天数要求：尝试更小的运载能力，收缩右边界
                    right = mid;
                } else {
                    // 不满足要求：必须增大运载能力，收缩左边界
                    left = mid + 1;
                }
            }
            return left;
        }

        private int f(int[] weights, int capacity) {
            int days = 0;
            for (int i = 0; i < weights.length;) {
                int cap = capacity;
                while (i < weights.length) {
                    // 装不下当前包裹，结束本批次运输
                    if (cap < weights[i]) {
                        break;
                    } else {
                        cap -= weights[i];
                    }
                    i++;
                }
                // 完成一趟运输，天数+1
                days++;
            }
            return days;
        }