LintCode 1676 · Skip Stones.java

	public class Solution {
	/**
	* @param n: The total number of stones.
	* @param m: The total number of stones you can remove.
	* @param target: The distance from the end to the starting point.
	* @param d: The array that the distance from the i rock to the starting point is d[i].
	* @return: Return the maximum value of the shortest jump distance.
	*/
	public int getDistance(int n, int m, int target, List<Integer> d) {
	// handle corner cases
	if (m >= n) {
	return target;
	}
	// binarySearch on the result space.
	int begin = 0, end = target;
	while (begin + 1 < end) {
	int mid = (end - begin) / 2 + begin;
	if (numberOfRemovals(n, mid, target, d) <= m) {
	begin = mid;
	} else {
	end = mid;
	}
	}
	// System.out.println("begin=" + begin + "; end=" + end);
	if (numberOfRemovals(n, end, target, d) <= m) {
	return end;
	}
	if (numberOfRemovals(n, begin, target, d) <= m) {
	return begin;
	}
	return target;
	}
	private int numberOfRemovals(int n, int minDistanceRequired, int target, List<Integer> D) {
	// calculating the numberOfRemovals, if we were to achieve that minDistanceRequired.
	int removalCounter = 0;
	int lastLocation = 0;
	for (int currentLocation : D) {
	if (currentLocation - lastLocation < minDistanceRequired) {
	removalCounter++;
	} else {
	lastLocation = currentLocation;
	}
	}
	// System.out.println("removalCounter=" + removalCounter + "; minDistanceRequired=" + minDistanceRequired);
	return removalCounter;
	}
	}

view raw LintCode 1676 · Skip Stones.java hosted with ❤ by GitHub