Minimum Ship Capacity to Deliver Packages Within D Days

A conveyor belt loads packages onto a ship in the fixed order given; the i-th package weighs weights[i]. All packages must be shipped within exactly D days. Each day, packages are loaded in order onto the ship, and the total weight loaded that day cannot exceed the ship's capacity; loading for the day stops as soon as adding the next package would exceed capacity, and a new day begins with that package. Find the minimum ship capacity that allows all packages to be shipped within D days.

Input: The first line contains two integers n and D. The second line contains n space-separated integers, the package weights in loading order. Output: Print a single integer: the minimum ship capacity.

1 <= n <= 5*10^4 (n = number of packages) 1 <= D <= n 1 <= weights[i] <= 500

The packages must be loaded in the GIVEN FIXED ORDER (not freely rearranged) - this constraint is exactly what makes the greedy 'fill each day until it would overflow' feasibility check valid and simple, unlike a problem that allowed rearranging packages freely.

Find the smallest ship capacity that still lets all packages (loaded in a fixed order) be delivered within a given number of days. Brute force: Try every possible capacity starting from the heaviest single package upward, checking feasibility for each - this costs O(sum of weights * n) in the worst case, too slow for large inputs. Optimised: Since the number of days needed is a MONOTONIC (non-increasing) function of capacity, binary searching directly on capacity - checking feasibility with an O(n) greedy day-count simulation at each candidate - finds the minimum feasible capacity in O(n log(sum of weights)).

1. The capacity can never be smaller than the SINGLE HEAVIEST package (it must fit alone if needed), and never needs to be larger than the SUM of all weights (fitting everything in one day) - binary search that range. 2. For a candidate capacity, greedily load packages in the GIVEN ORDER onto the current day until the next one would overflow it, then start a new day; count how many days this takes. 3. Since the number of days needed only DECREASES as capacity increases (monotonic), binary search for the smallest capacity whose day count is <= D.

Time: O(n log(sum of weights)) - each binary search step's greedy feasibility check costs O(n). Space: O(1) extra space beyond the input array.

D = 1 (capacity must equal the sum of all weights); D = n (capacity only needs to equal the heaviest single package, or possibly less is never valid since it can never go below the max).

Be ready to connect this directly to 'Painter's Partition' and 'Book Allocation' - all three are the EXACT same binary-search-on-the-answer-plus-greedy-feasibility-check pattern, just with different real-world framing and a slightly different feasibility formula.