LeetCode 1891. 割繩子(二分查找)

Michael阿明 2021-08-15 22:28:31 阅读数:105

本文一共[544]字,预计阅读时长:1分钟~
leetcode 二分 查找

文章目錄

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阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753169o.html