孝感网站制作,1688货源网,高端网站建设公司怎么做推广,公司外文网站制作文章目录1. 题目2. 解题1. 题目
给定一个整数数组 ribbons 和一个整数 k#xff0c;数组每项 ribbons[i] 表示第 i 条绳子的长度。
对于每条绳子#xff0c;你可以将任意切割成一系列长度为正整数的部分#xff0c;或者选择不进行切割。
例如#xff0c;如果给你一条长度…
文章目录1. 题目2. 解题1. 题目
给定一个整数数组 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 10^5
1 ribbons[i] 10^5
1 k 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/cutting-ribbons 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
绳子长度 len 变长那么得到的绳子的根数 k 不会变多具有单调性进行二分查找
class Solution {
public:int maxLength(vectorint ribbons, int k) {int l 1, r 1e5, len, ans 0;while(l r){len (lr)1;if(ok(ribbons, len, k)){l len1;ans len;}elser len-1;}return ans;}bool ok(vectorint ribbons, int len, int k){int ct 0;for(auto r : ribbons){ct r/len;if(ct k)return true;}return false;}
};152 ms 90.3 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
