Leetcode

Leetcode 774. Minimize Max Distance to Gas Station

chenboxieLeave a comment

https://leetcode.com/problems/minimize-max-distance-to-gas-station/description/

https://www.cnblogs.com/grandyang/p/6854825.html
这个文章总结了二分搜索法的几个分类

1. 对于搜索类的题目，如果我们知道答案ans所在的区间[lo, hi]，并且给定一个值y，我们有比较效率的算法可以验证y是否是ans的上/下界，那么通常binary search都是值得考虑的算法。
2. 这是一个经典的二分问题，看到最小化最大值以及最大化最小值问题的时候，通常要想到二分法

 

接下来的这段总结来自于Leetcode Discuss的fun4leetcode的总结
https://leetcode.com/problems/minimize-max-distance-to-gas-station/discuss/113629/Approach-the-problem-using-the-%22trial-and-error%22-algorithm
也就是说，第一步要先找到答案所在的区间，最大最小值[min, max], 然后二分mid，第二步比较困难，要想到如何根据题目条件，判断出这个mid是否是答案，如果不是，该往上还是往下走。

I -- Construct a candidate solution

To construct a candidate solution, we need to understand first what the desired solution is. The problem description requires we output the minimum value of the maximum distance between adjacent gas stations. This value is nothing more than a non-negative double value, since the distance between any adjacent stations cannot be negative and in general it should be of double type. Therefore our candidate solution should also be a non-negative double value.

II -- Search space formed by all the candidate solutions

Let max be the maximum value of the distances between any adjacent stations without adding those additional stations, then our desired solution should lie within the range [0, max]. This is because adding extra stations (and placing them at proper positions) can only reduce the maximum distance between any adjacent stations. Therefore our search space will be [0, max] (or the upper bound should be at least max).

III -- Verify a given candidate solution

This is the key part of this trial and error algorithm. So given a candidate double value d, how do we determine if it can be the minimum value of the maximum distance between any adjacent stations after adding K extra stations? The answer is by counting.

If d can be the minimum value of the maximum distance between any adjacent stations after adding K extra stations, then the following two conditions should be true at the same time:

  1. The total number of stations we can add between all adjacent stations cannot go beyond K. In other words, assume we added cnt_i stations in between the pair of adjacent stations (i, i+1), then we should have sum(cnt_i) <= K.
  2. For each pair of adjacent stations (i, i+1), the minimum value of the maximum distance between adjacent stations after adding cnt_i additional stations cannot go beyond d. If the original distance between station i and i+1 is d_i = stations[i+1] - stations[i], then after adding cnt_i additional stations, the minimum value of maximum distance between any adjacent stations we can obtain is d_i / (cnt_i + 1), which is achieved by placing those stations evenly in between stations i and i+1. Therefore we require: d_i / (cnt_i + 1) <= d, which is equivalent to cnt_i >= (d_i/d - 1).

So you can see that the two conditions are actually “contradictory” to each other: to meet condition 1, we want cnt_i to be as small as possible; but to meet condition 2, we’d like it to be as large as possible. So in practice, we can alway choose the set of smallest cnt_i‘s that satisfy the second condition and double check if they also meet the first condition. If they do, then d will set an upper limit on the final minimum value obtainable; otherwise d will set a lower limit on this minimum value.

This verification algorithm runs at O(n), where n is the length of the stations array. This is acceptable if we can walk the search space very efficiently (which can be done at the order of O(log(max/step)), with step = 10^-6). In particular, this is much faster than the straightforward O(Klogn) solution where we add the stations one by one in a greedy manner (i.e., always reduce the current maximum distance first), given that K could be orders of magnitude larger than n (note this greedy algorithm can be optimized to run at O(nlogn), see wannacry89’s post here).

相似题目：
1. https://leetcode.com/problems/guess-number-higher-or-lower/description/
2. https://leetcode.com/problems/maximum-average-subarray-ii/description/
这道题的一个子问题要记住一下做法：在一个array中找到长度大于或者等于k的subarray, 使得subarray里的和大于零。在判断某个平均值是否满足时，转换为求连续子数组的和大于0

private boolean check(int[] nums, int k, double mid) {
double sum = 0, prev = 0, minPrev = 0;
for (int i = 0; i < k; i++) {
sum += nums[i] – mid;
}
if (sum >= 0) return true;
for (int i = k; i < nums.length; i++) {
sum += nums[i] – mid;
prev += nums[i – k] – mid;
minPrev = Math.min(prev, minPrev);
if (sum >= minPrev) {
return true;
}
}
return false;
}

3. https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/
4. https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/

Leave a comment