05 August 2008
给定一个整数数组ribbons，其中ribbons[i] 表示第i 个ribbon 的长度，以及一个整数k。您以将任何个ribbon切割成任意数量的正整数长度段，或者根本不进行切割。
例如，如果有一条长度为 4 的色带，可以：
保留长度为 4 的丝带，
把它剪成一根长度为3的丝带和一根长度为1的丝带，
把它剪成两条长度为2的丝带，
将其切成一条长度为 2 的丝带和两条长度为 1 的丝带，或
把它剪成四个长度为1的丝带。
您的目标是获得所有相同正整数长度的 k 个色带。由于切割，您可以扔掉多余的色带。
返回可以获得的 k 个色带的最大可能正整数长度，如果无法获得相同长度的 k 个色带，则返回 0。
check if the sum is greater than k or not, otherwise for case [5,7,9], k = 22, it may return 1 as it will exit the loop with left = right = 1, while it really should be 0.
Avoid infinite loop: the way we compute middle pivot should be mid = right - (right - left) / 2, basically leaning to the right side and it will get out of the loop with left = mid and right = mid - 1. Usually when we are using lower bound, it would be left + (right - left) / 2. From this article: https://medium.com/swlh/binary-search-find-upper-and-lower-bound-3f07867d81fb, “When we select the former one using l+(r-l)/2, we want to make sure to avoid l = mid because that might lead to infinite loop. For example when there are two elements [0,1] and mid=0, then l becomes mid and the iteration goes again and again.
Similarly, when we select the latter one using r-(r-l)/2, we want to avoid r=mid.”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public int maxLength(int[] ribbons, int k) {
long right = 0;
long sum = 0;
for (int r : ribbons) {
sum += r;
right = Math.max(right, r);
}
if (k >= sum) {
return sum == k ? 1 : 0;
}
long left = 1;
while (left < right) {
long mid = right - (right - left) / 2;
if (canCutKRibbons(ribbons, k, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return (int) left;
}
private boolean canCutKRibbons(int[] ribbons, int k, long length) {
int count = 0;
for (int ribbon : ribbons) {
count += ribbon / length;
}
return count >= k;
}
}