README.md

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

解法

“二分法”实现。

Python3

class Solution:
    def maxLength(self, ribbons: List[int], k: int) -> int:
        low, high = 0, 100000
        while low < high:
            mid = (low + high + 1) >> 1
            cnt = 0
            for ribbon in ribbons:
                cnt += ribbon // mid
            if cnt < k:
                high = mid - 1
            else:
                low = mid
        return low

Java

class Solution {
    public int maxLength(int[] ribbons, int k) {
        int low = 0, high = 100000;
        while (low < high) {
            int mid = (low + high + 1) >> 1;
            int cnt = 0;
            for (int ribbon : ribbons) {
                cnt += ribbon / mid;
            }
            if (cnt < k) {
                high = mid - 1;
            } else {
                low = mid;
            }
        }
        return low;
    }
}

JavaScript

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

C++

class Solution {
public:
    int maxLength(vector<int>& ribbons, int k) {
        int low = 0, high = 100000;
        while (low < high) {
            int mid = (low + high + 1) / 2;
            int cnt = 0;
            for (auto ribbon : ribbons) {
                cnt += ribbon / mid;
            }
            if (cnt < k) {
                high = mid - 1;
            } else {
                low = mid;
            }
        }
        return low;
    }
};

Go

func maxLength(ribbons []int, k int) int {
	low, high := 0, 100000
	for low < high {
		mid := (low + high + 1) >> 1
		cnt := 0
		for _, ribbon := range ribbons {
			cnt += ribbon / mid
		}
		if cnt < k {
			high = mid - 1
		} else {
			low = mid
		}
	}
	return low
}

...