Question

1891. 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

Solutions

Solution 1: Binary Search

We observe that if we can obtain $k$ ropes of length $x$, then we can also obtain $k$ ropes of length $x-1$. This implies that there is a monotonicity property, and we can use binary search to find the maximum length $x$ such that we can obtain $k$ ropes of length $x$.

We define the left boundary of the binary search as $left=0$, the right boundary as $right=\max(ribbons)$, and the middle value as $mid=(left+right+1)/2$. We then calculate the number of ropes we can obtain with length $mid$, denoted as $cnt$. If $cnt \geq k$, it means we can obtain $k$ ropes of length $mid$, so we update $left$ to $mid$. Otherwise, we update $right$ to $mid-1$.

Finally, we return $left$ as the maximum length of the ropes we can obtain.

The time complexity is $O(n \times \log M)$, where $n$ and $M$ are the number of ropes and the maximum length of the ropes, respectively. The space complexity is $O(1)$.

class Solution:
  def maxLength(self, ribbons: List[int], k: int) -> int:
    left, right = 0, max(ribbons)
    while left < right:
      mid = (left + right + 1) >> 1
      cnt = sum(x // mid for x in ribbons)
      if cnt >= k:
        left = mid
      else:
        right = mid - 1
    return left

class Solution {
  public int maxLength(int[] ribbons, int k) {
    int left = 0, right = 0;
    for (int x : ribbons) {
      right = Math.max(right, x);
    }
    while (left < right) {
      int mid = (left + right + 1) >>> 1;
      int cnt = 0;
      for (int x : ribbons) {
        cnt += x / mid;
      }
      if (cnt >= k) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  int maxLength(vector<int>& ribbons, int k) {
    int left = 0, right = *max_element(ribbons.begin(), ribbons.end());
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      int cnt = 0;
      for (int ribbon : ribbons) {
        cnt += ribbon / mid;
      }
      if (cnt >= k) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
};

func maxLength(ribbons []int, k int) int {
  left, right := 0, slices.Max(ribbons)
  for left < right {
    mid := (left + right + 1) >> 1
    cnt := 0
    for _, x := range ribbons {
      cnt += x / mid
    }
    if cnt >= k {
      left = mid
    } else {
      right = mid - 1
    }
  }
  return left
}

function maxLength(ribbons: number[], k: number): number {
  let left = 0;
  let right = Math.max(...ribbons);
  while (left < right) {
    const mid = (left + right + 1) >> 1;
    let cnt = 0;
    for (const x of ribbons) {
      cnt += Math.floor(x / mid);
    }
    if (cnt >= k) {
      left = mid;
    } else {
      right = mid - 1;
    }
  }
  return left;
}

impl Solution {
  pub fn max_length(ribbons: Vec<i32>, k: i32) -> i32 {
    let mut left = 0i32;
    let mut right = *ribbons.iter().max().unwrap();
    while left < right {
      let mid = (left + right + 1) / 2;
      let mut cnt = 0i32;
      for &entry in ribbons.iter() {
        cnt += entry / mid;
        if cnt >= k {
          break;
        }
      }
      if cnt >= k {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
}

/**
 * @param {number[]} ribbons
 * @param {number} k
 * @return {number}
 */
var maxLength = function (ribbons, k) {
  let left = 0;
  let right = Math.max(...ribbons);
  while (left < right) {
    const mid = (left + right + 1) >> 1;
    let cnt = 0;
    for (const x of ribbons) {
      cnt += Math.floor(x / mid);
    }
    if (cnt >= k) {
      left = mid;
    } else {
      right = mid - 1;
    }
  }
  return left;
};