1891. Cutting Ribbons

binary search

time: O(nlogn), getCount use O(n), inside binary search, so O(nlogn)

space: O(1)

range: 1~ max ribbons len,

optimized, use Math.min(end, sum/k)

notice edge case : sum < k

1. find range in 1~9
2. 
      [7,5,9], k = 4
      
      1+ (9-1)/2  = 5, len = 5
      
      3 < k, so abandon right
      right = mid = 5, 1~5
      
      1 + (5-1)/2 = 3
      
      6 >= k, so abandon left
      start = mid, 3~5
      
      3 + (5-3)/2 = 4
      
      4 >= k, so start = mid = 4, go out while
      
      at last choose start or end
      
      
   1 2 3 4 5 6  <= cut len
7  7 3 2 1 1
5  5 2 1 1 1
9  9 4 3 2 1
k 21 9 6 4 3  . so k(段數) = 3, choose len 5




      [5,7,9], k = 22

cant!

class Solution {
    public int maxLength(int[] ribbons, int k) {
        int start = 1;
        int end = 0;
        long sum = 0; // 注意, sum 要 long, test data 很大
        for (int ribbon : ribbons) {
            end = Math.max(end, ribbon); // end just set to max ribbons' len
            sum += ribbon;
        }
        
        // if has this, the ans will be the best
        // end  = (int)Math.min(end, sum/k);
        // if (end < 1) { // edge case check same as sum < k return 0
        //     return 0;
        // }
        
        if (sum < k) { //notice this, edge case
            return 0;
        }
        
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            if (getCount(ribbons, mid) >= k) { // get more than k, means mid(len) can be larger
                start = mid;
            } else {
                end = mid;
            }
        }
        return getCount(ribbons, end) >= k ? end : start;
    }

    private int getCount(int[] ribbons, int len) {
        int count = 0;
        for (int ribbon : ribbons) {
            count += ribbon/len;
        }
        return count;
    }
    
}

因為如果 end 符合, 優先回 end , 因為答案要長一點的

return getCount(ribbons, end) >= k ? end : start;