前言
今天分享一道木棍切割问题。
此题经常在字节跳动后端面试中遇到，尤其是字节-教育部门-三面。我感觉之后面试还会考察这道题。
其他的大厂高频题可以在 CodeTop 查看
废话不多说，直接开讲。
题目描述
给定长度为n的数组，每个元素代表一个木头的长度，木头可以任意截断，从这堆木头中截出至少k个相同长度为m的木块。已知k，求max(m)。
ps: 截断的长度必须是整数
输入两行，第一行n, k，第二行为数组序列。输出最大值。
输入
5 5
4 7 2 10 5
输出
4
解释：如图，最多可以把它分成5段长度为4的木头
.png)
ps:数据保证有解，即结果至少是1。
题目分析
方法一：暴力。 大概思路就是从1遍历到木棍最长的长度，每次遍历的长度作为m，如果可以将所有木头截出来k个长度为m的木块，则更新最大值，最后输出最大值即可。可以通过下面的伪代码片段辅助理解：
// input n, k;
int maxV = max(a[0 ~ n - 1]);
int res = 0;
int m = 1;
while (m <= maxV)
{
int cnt = 0;
for (int i = 0; i < n; i ++ ) cnt += a[i] / m;
if (cnt >= k) res = max(res, m); // 如果当前可以截出来超过k段，就更新结果
m ++;
}
cout << res << endl;上面的代码也比较容易理解，这里就不多展开说了。时间复杂度也很容易看出来是O(n * len), len为木头中最大的长度。容易想到遍历长度时可以从大到小遍历，if (cnt >= k)成立，则该值即为最终结果，可直接break，但最坏时间复杂度没变。
方法二：二分。 方法一在[1,max]寻找最大长度时是顺序遍历，由于其有序，我们可借助二分来快速检出结果。如果能截出来k个长度为x的木块，说明答案肯定 >= x，则接下来只需在[x,max]中找m最大满足条件的长度。反之则说明答案 < x，则在[1,x-1]中寻找结果。这样我们每次可以舍弃1/2的情况，因此使用二分的时间复杂度是O(n * log Len)。
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int n, k;
int check(int mid)
{
int res = 0;
for (int i = 0; i < n; i ++ ) res += a[i] / mid;
return res;
}
int main()
{
cin >> n >> k;
int l = 1, r = -1;
for (int i = 0; i < n; i ++ )
{
cin >> a[i];
r = max(r, a[i]);
}
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid) >= k) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}评论 (13)
