1011. Capacity To Ship Packages Within D Days

class Solution:
    def shipWithinDays(self, A: List[int], D: int) -> int:
        """tc O(Nlg(sum(A))) sc O(1)
        find min capacity to carry all weights in A and total time cost <= D
        => estimate capacity = ceil ((total weight) /D )
        constrains:  each package a is not splitable   => left pointer need to be bigger than any single package weight 
                        use Binary Search to adjust capacity 
        how about right ptr?  sum of A
        1. get sum of A and average of A 
        2. get mid and count time cost to ship all packages based on the mid capacity
        3. find smallest valid mid 
        """
        sumA,avg = sum(A),(sum(A)+D-1)//D # can optimize by one round 
        l,r = max(avg,max(A)), sumA #+1
        while l < r:
            mid = l + (r-l)//2
            days,load = 1,0
            for a in A:

                if load + a <= mid:
                    load += a 
                else:
                    days += 1
                    load = a # single a can be larger than capcacity
                   
            if days > D: # capacity is too small
                l = mid + 1 
            else:
                r = mid 
        return l