LeetCode 1891. 割绳子（二分查找）

Michael阿明

发布于 2021-09-06 11:36:20

1.9K0

发布于 2021-09-06 11:36:20

文章被收录于专栏：Michael阿明学习之路

文章目录

- 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(vector<int>& ribbons, int k) {
        int l = 1, r = 1e5, len, ans = 0;
        while(l <= r)
        {
            len = (l+r)>>1;
            if(ok(ribbons, len, k))
            {
                l = len+1;
                ans = len;
            }
            else
                r = len-1;
        }
        return ans;
    }
    bool ok(vector<int>& 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阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/08/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https