# FB两轮店面面筋附面筋整理

10/29 第一轮 印度小哥哥

11/8 第二轮，人超好的国人小哥

wood cut

lz太棒啦，加油！对了，问下一二面都有bq吗

``````	/**
* Wood Cut Given n pieces of wood with length L[i] (integer array). Cut
* them into small pieces to guarantee you could have equal or more than k
* pieces with the same length. What is the longest length you can get from
* the n pieces of wood? Given L & k, return the maximum length of the small
* pieces. Priorities: 1. Have to get calculatedK >= givenK 2. Meanwhile,
* want to maximize the small piece. One thing not clear: do we have to use
* the given small piece? If we have to, we need to concern about the
* shortest wood piece. See commentted-out part In this problem, however, we
* can abandon the small pieces, as long as the max_small_pieces can allow
* calculatedK >= givenK. Use binary search on the largest item: 1. if
* calculatedK < givenK: end = mid; 2. If calculated >= givenK, move start =
* mid as much as possible, which gives maximized small piece.

start = 0, end = 5, wrong 4
L [5], k = 1
*/
public int woodCut(int[] L, int k) {
int end = 0;

for (int len : L) {
end = Math.max(end, len);
}

if (numWood(end, L) >= k) {
return end;
}

// trying to cut with length 1 - max
int start = 0;
while (start + 1 < end) {
int mid = start + ((end - start) >>> 1);
int numMid = numWood(mid, L);
if (numMid >= k) {
start = mid;
} else {
end = mid;
}
}

return start;
}

private int numWood(int length, int[] L) {
int count = 0;
for (int len : L) {
count += len / length;
}
return count;
}``````

woods: (5, 9, 7), k = 3; return 5; (5->5; 9->5+4; 7->5+2)
woods: (5, 9, 7), k = 4; return 4; (5->4+1; 9->4*2+1; 7->4+3)