LeetCode 1011
二分查找
引用
官方题解和宫水三叶的题解
设 「D天内运送完所有包裹的最低运力」是 ans ，则有如下两种情况：
- 数值范围在
的运力必然「不满足」
D天内运送完所有包裹的要求 - 数值范围在
的运力必然「满足」
D天内运送完所有包裹的要求
所以可以用「二分查找」来确定 ans
然后确定二分查找的左右边界，即「运力」的极值。
- 最低运力：运力ans必定大于所有包裹中的「最大重量」，否则该包裹运不走。
- 最高运力：运力ans必定小于所有包裹的「重量总和」，这样一天就可以全部运走，是效率最高的方式。
在二分过程中，将当前运力取中间值，然后对重量迭代遍历一遍，运用贪心思想，直到一天中的重量比当前运力重，则将最后的那个箱子放到「第二天」。
最后将需要的总天数与规定的上限天数 D 比较。
- 总天数
needDays比 D小，说明可以提前运完，运力大了，右边界左移，将每天称重减小。 - 总天数
needDays比 D大，说明在规定天内运不完，运力小了，左边界右移，将每天称重增大。
public class Solution {
public int shipWithinDays(int[] weights, int D) {
int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
while (left <= right) {
int mid = (left + right) / 2; /** current weighting capacity */
/** Days required & Total weigth per day */
int needDays = 1, totalWeigthPerDay = 0;
for (int weight : weights) {
/** Too heavy, pass next day */
if (totalWeigthPerDay + weight > mid) {
needDays++;
totalWeigthPerDay = 0;
}
totalWeigthPerDay += weight;
}
if (needDays <= D)
right = mid - 1; /** reduce weight per day */
else
left = mid + 1; /** increase weigth per day */
}
return left;
}
}
