# 774.Minimize-Max-Distance-to-Gas-Station

## 774. Minimize Max Distance to Gas Station

## 题目地址

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

## 题目描述

```
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 = 9
Output: 0.500000

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

## 代码

### Approach #1 Dynamic Programming \[Memory Lmit Exceeded]

Time: O(NK^2) && Space: O(NK)

```java
class Solution {
  public double minmaxGasDist(int[] stations, int K) {
        int N = stations.length;
    double[] deltas = new double[N-1];
    for (int i = 0; i < N-1; i++) {
      deltas[i] = stations[i+1] - stations[i];
    }
    double[][] dp = new double[N-1][K+1];
    for (int i = 0; i <= K; i++)
      dp[0][i] = deltas[0] / (i+1);

    for (int p = 1; p < N-1; p++) {
      for (int k = 0; k <= K; k++) {
        double bns = 999999999;
        for (int x = 0; x <= k; x++) {
          bns = Math.min(bns, Math.max(deltas[p] / (x+1), dp[p-1][k-x]));
        }
        dp[p][k] = bns;
      }
    }

    return dp[N-2][K];
  }
}
```

### Approach #2 Binary Search

```java
class Solution {
  public double minmaxGasDist(int[] stations, int K) {
        int count;
    int N = stations.length;
    double left = 0;
    double right = stations[N-1] - stations[0];
    while (right - left > 1e-6) { //  left - right < 1e-6 TLE
      double mid = (left + right) / 2;
      count = 0;
      for (int i = 0; i < N-1; i++) {
        count += (int)((stations[i+1] - stations[i]) / mid);
      }
      if (count > K) {
        left = mid;
      } else {
        right = mid;
      }
    }
    return right;
  }
}
```

### Approach #3 PriorityQueue Greedy \[Time Limit Exceeded]

```java
public double minmaxGasDist(int[] stations, int K) {
  PriorityQueue<double[]> pq = new PriorityQueue<double[]>(
      (a,b) -> (a[0]/a[1] < b[0]/b[1]) ? 1 : -1);     
  for (int i = 1; i < stations.length; ++i) {
    pq.add(new double[] {stations[i] - stations[i-1], 1.0});     
  } 
  while (K-- > 0) {
    double [] cur = pq.poll();
    ++cur[1];
    pq.add(cur);
  }
  double[] value =  pq.poll();
  return value[0] / value[1];
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/dynamic-programming/774.minimize-max-distance-to-gas-station.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.