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

【代码描述】

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

​​https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/​​

【示例】

【代码】

​​学习参考​​

import java.util.*;

/**
* 2022-12-08
*/

class Solution {

public int shipWithinDays(int[] weights, int days) {
int left = 0;
int right = 0;

for (int x: weights) {
left = Math.max(left, x);
right = right + x;
        }

while (left < right){
int mid = (right - left) / 2 + left;
if (finish(weights, days, mid)){
right = mid;
            }else {
left = mid + 1;
            }
        }
return left;
    }

private boolean finish(int[] weights, int days, int mid) {
int use = 0;
int day = 1;

for (int weight : weights) {
if (use + weight <= mid){
use += weight;
            }else {
day++;
use = weight;
            }
if (day > days) return false;
        }
return true;
    }
}

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

int[] arr1 = {3,2,2,4,1,4};
int days1 = 3;
System.out.println(new Solution().shipWithinDays(arr1, days1));  // 输出 6
    }
}

【二分法】

import java.util.*;

/**
* 2022-12-08
*/

class Solution {
// 返回目标在数组arr中的下标
public int erfenfa(int[] arr, int target, int start, int end) {
int mid = (end - start) / 2 + start;
// 如果刚好相等，直接返回
if (arr[mid] == target){
return mid;
        }

if (target > arr[mid]){
return erfenfa(arr, target, mid + 1, end);
        }

if (target <= arr[mid]){
return erfenfa(arr, target, start, mid - 1);
        }
// 未找到返回 -1
return -1;
    }
}

public class Main {
public static void main(String[] args) {
int[] arr = {1,21,3,34,57,56,7,18,94,10};
int target = 57;
// 一定是个有序数组
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
System.out.println(new Solution().erfenfa(arr, target, 0, arr.length - 1));  // 输出 15

    }
}