https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
思路:
分析题目有两个临界值,容量足够,能够送达;容量不够,不能送达。我们要找的那个容量是满足条件的最小容量,可以考虑使用二分法。
/** * 切分成 D 段,求满足条件的最小容量 * 这道题有两个临界值,最小值是物品中的最大重量。最小值是所有物品重量的和 * 可以考虑使用二分法,逐渐逼近正确值 */ class Solution { public int shipWithinDays(int[] weights, int D) { int left = Integer.MIN_VALUE, right = 0; for(int w : weights){ left = Math.max(left, w); right += w; } while(left < right){ //mid 就是我们进行试探的值 int mid = (left + right) / 2; //下面就是一个判断条件 int need = 0;//需要的运输次数 int cur = 0; for(int i = 0; i < weights.length; i++){ //已经超出了最大运载能力 if(cur + weights[i] > mid){ need ++; cur = 0; } cur += weights[i]; } //当前的 mid 满足条件,说明我们的运载能力是足够的 if(need < D){ right = mid; } else{ left = mid + 1; } } return left; } }