Problem:

On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = stations.length.

Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of D.

Example:

Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9Output: 0.500000

Note:

1. stations.length will be an integer in range [10, 2000].
2. stations[i] will be an integer in range [0, 10^8].
3. K will be an integer in range [1, 10^6].
4. Answers within 10^-6 of the true value will be accepted as correct.

Solution:

　　这道题是用了一种非常规的Binary Search解法。最开始我想用一种贪心算法，每次找出间隔最大的两站然后做二分，但这个思路是不对的，比如1，7，K等于2时，如果做二分的话会在4，2.5的位置依次放两站，其结果为3，而实际上只需要在3，5依次放两站其结果为2。因此这个算法不正确。答案用的是一种非常巧妙的二分搜索，二分搜索的是当最大间距为pivot时，需要放置的station的数量。如果需要放置的数量大于K，说明pivot值过小，需要在pivot和right之间继续寻找这个最大间距，否则在left和pivot中二分查找。最后得到的结果就是在放置K个station时最小化的最大间距。这道题和我们的常规想法不同，平时对于一般的问题，我们都是根据已知条件去计算这个结果，而这道题算是逆向思维，它先假设一个结果然后去判断其是否满足条件。这也是这道题评为hard的原因吧。

Code:

 

1 class Solution { 2 public: 3     double minmaxGasDist(vector
     
      & stations, int K) { 4         double left = 0; 5         double right = stations.back()-stations[0]; 6         while(right-left > 1e-6) { 7             double pivot = left+(right-left)/2; 8             int count = 0; 9             for(int i = 1;i != stations.size();++i){10                 count += (stations[i]-stations[i-1])/pivot;11             }12             if(count <= K)13                 right = pivot;14             else15                 left = pivot;16         }17         return left;18     }19 };