脸熟店面

直接上题:

Given an int array wood representing the length of n pieces of wood and an int k. It is required to cut these pieces of wood such that more or equal to k pieces of the same length len are cut. What is the longest len you can get?

Example 1:

Input: wood = [5, 9, 7], k = 3
Output: 5
Explanation:
5 -> 5
9 -> 5 + 4
7 -> 5 + 2
Example 2:

Input: wood = [5, 9, 7], k = 4
Output: 4
Explanation:
5 -> 4 + 1
9 -> 4 * 2 + 1
7 -> 4 + 3

binary search ?


	/**
	 * 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;
	}