package Leetcode.BinarySearch;

import java.util.Arrays;

/**
 * @author zhengstars
 * @date 2024/01/28
 */
public class Capacity {
    public static int shipWithinDays(int[] weights, int D) {
        // Determine the initial lower and upper bounds of the binary search.
        // The lower bound (left) is the maximum weight in the array.
        // The upper bound (right) is the sum of all weights.
        int left = Arrays.stream(weights).max().getAsInt();
        int right = Arrays.stream(weights).sum();

        // Perform the binary search.
        while (left < right) {
            // Calculate the middle point.
            int mid = left + (right - left) / 2;

            // Initialize the number of days needed to 1 and the current weight to 0.
            int need = 1;
            int cur = 0;

            // Loop through the weights array.
            for (int weight : weights) {
                // If the current sum of weights is greater than mid, we need to increase the day count and reset the current weight.
                if (cur + weight > mid) {
                    need++;
                    cur = 0;
                }
                // Add the weight to the current weight.
                cur += weight;
            }

            // If the number of days needed exceeds D, we need to increase the lower bound of the binary search.
            // Otherwise, we can decrease the upper bound.
            if (need > D) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // Return the optimal ship weight capacity.
        return left;
    }

    public static void main(String[] args) {
        // Test Case 1
        System.out.println(shipWithinDays(new int[]{1,2,3,4,5,6,7,8,9,10}, 5)); // Output: 15

        // Test Case 2
        System.out.println(shipWithinDays(new int[]{3,2,2,4,1,4}, 3)); // Output: 6

        // Test Case 3
        System.out.println(shipWithinDays(new int[]{1,2,3,1,1}, 4)); // Output: 3
    }
}