Question

1891. 割绳子

English Version

题目描述

给定一个整数数组 ribbons 和一个整数 k，数组每项 ribbons[i] 表示第 i 条绳子的长度。对于每条绳子，你可以将任意切割成一系列长度为正整数的部分，或者选择不进行切割。

例如，如果给你一条长度为 4 的绳子，你可以：

• 保持绳子的长度为 4 不变；
• 切割成一条长度为 3 和一条长度为 1 的绳子；
• 切割成两条长度为 2 的绳子；
• 切割成一条长度为 2 和两条长度为 1 的绳子；
• 切割成四条长度为 1 的绳子。

你的任务是最终得到 k 条完全一样的绳子，他们的长度均为相同的正整数。如果绳子切割后有剩余，你可以直接舍弃掉多余的部分。

对于这 k 根绳子，返回你能得到的绳子最大长度；如果你无法得到 k 根相同长度的绳子，返回 0。

 

示例 1:

输入: ribbons = [9,7,5], k = 3
输出: 5
解释:
- 把第一条绳子切成两部分，一条长度为 5，一条长度为 4；
- 把第二条绳子切成两部分，一条长度为 5，一条长度为 2；
- 第三条绳子不进行切割；
现在，你得到了 3 条长度为 5 的绳子。

示例 2:

输入: ribbons = [7,5,9], k = 4
输出: 4
解释:
- 把第一条绳子切成两部分，一条长度为 4，一条长度为 3；
- 把第二条绳子切成两部分，一条长度为 4，一条长度为 1；
- 把第二条绳子切成三部分，一条长度为 4，一条长度为 4，还有一条长度为 1；
现在，你得到了 4 条长度为 4 的绳子。

示例 3:

输入: ribbons = [5,7,9], k = 22
输出: 0
解释: 由于绳子长度需要为正整数，你无法得到 22 条长度相同的绳子。

 

提示:

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

解法

方法一：二分查找

我们发现，如果我们能够得到长度为 $x$ 的 $k$ 根绳子，那么我们一定能够得到长度为 $x - 1$ 的 $k$ 根绳子，这存在着单调性。因此，我们可以使用二分查找的方法，找到最大的长度 $x$，使得我们能够得到长度为 $x$ 的 $k$ 根绳子。

我们定义二分查找的左边界 $left=0$, $right=\max(ribbons)$，中间值 $mid=(left+right+1)/2$，然后计算当前长度为 $mid$ 的绳子能够得到的数量 $cnt$，如果 $cnt \geq k$，说明我们能够得到长度为 $mid$ 的 $k$ 根绳子，那么我们将 $left$ 更新为 $mid$，否则我们将 $right$ 更新为 $mid-1$。

最后，我们返回 $left$ 即可。

时间复杂度 $O(n \times \log M)$，其中 $n$ 和 $M$ 分别为绳子的数量和绳子的最大长度。空间复杂度 $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;
};