LeetCode 1891. Cutting Ribbons

原题链接在这里：https://leetcode.com/problems/cutting-ribbons/description/

题目：

You are given an integer array ribbons, where ribbons[i] represents the length of the ith ribbon, and an integer k. You may cut any of the ribbons into any number of segments of positive integer lengths, or perform no cuts at all.

• For example, if you have a ribbon of length 4, you can:
  • Keep the ribbon of length 4,
  • Cut it into one ribbon of length 3 and one ribbon of length 1,
  • Cut it into two ribbons of length 2,
  • Cut it into one ribbon of length 2 and two ribbons of length 1, or
  • Cut it into four ribbons of length 1.

Your goal is to obtain k ribbons of all the same positive integer length. You are allowed to throw away any excess ribbon as a result of cutting.

Return the maximum possible positive integer length that you can obtain k ribbons of, or 0 if you cannot obtain k ribbons of the same length.

Example 1:

Input: ribbons = [9,7,5], k = 3
Output: 5
Explanation:
- Cut the first ribbon to two ribbons, one of length 5 and one of length 4.
- Cut the second ribbon to two ribbons, one of length 5 and one of length 2.
- Keep the third ribbon as it is.
Now you have 3 ribbons of length 5.

Example 2:

Input: ribbons = [7,5,9], k = 4
Output: 4
Explanation:
- Cut the first ribbon to two ribbons, one of length 4 and one of length 3.
- Cut the second ribbon to two ribbons, one of length 4 and one of length 1.
- Cut the third ribbon to three ribbons, two of length 4 and one of length 1.
Now you have 4 ribbons of length 4.

Example 3:

Input: ribbons = [5,7,9], k = 22
Output: 0
Explanation: You cannot obtain k ribbons of the same positive integer length.

Constraints:

• 1 <= ribbons.length <= 105
• 1 <= ribbons[i] <= 105
• 1 <= k <= 109

题解：

Keey trying with binary search.

l = 1, r = max(ribbons) + 1.

Guess a mid length, accumulate the count, if the count < k. This means the guess length is still too long, r = mid.

Otherwise, l = mid + 1.

Eventually return l - 1.

Note: since return l - 1, then r neds to be max(ribbons) + 1. Otherwise, [1, 1, 1], k = 3, it will return 0.

Time Complexity: O(n + log(max(ribbons))). n = ribbons.length.

Space: O(1).

AC Java:

 1 class Solution {
 2     public int maxLength(int[] ribbons, int k) {
 3         if(ribbons == null || ribbons.length == 0 || k <= 0){
 4             return 0;
 5         }
 6 
 7         int l = 1;
 8         int r = 1;
 9         for(int rib : ribbons){
10             r = Math.max(r, rib);
11         }
12 
13         r++;
14 
15         while(l < r){
16             int mid = l + (r - l) / 2;
17             if(getCount(ribbons, mid) < k){
18                 r = mid;
19             }else{
20                 l = mid + 1;
21             }
22         }
23 
24         return l - 1;
25     }
26 
27     private int getCount(int[] ribbons, int can){
28         int res = 0;
29         for(int rib : ribbons){
30             res += rib / can;
31         }
32 
33         return res;
34     }
35 }

类似Capacity To Ship Packages Within D Days.