LC: 774. Minimize Max Distance to Gas Station
https://leetcode.com/problems/minimize-max-distance-to-gas-station/
774. Minimize Max Distance to Gas Station
You are given an integer array stations that represents the positions of the gas stations on the x-axis. You are also given an integer k.
You should add k new gas stations. You can add the stations anywhere on the x-axis, and not necessarily on an integer position.
Let penalty() be the maximum distance between adjacent gas stations after adding the k new stations.
Return the smallest possible value of penalty(). Answers within 10-6 of the actual answer will be accepted.
Example 1:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000Example 2:
Input: stations = [23,24,36,39,46,56,57,65,84,98], k = 1
Output: 14.00000Constraints:
10 <= stations.length <= 20000 <= stations[i] <= 108stationsis sorted in a strictly increasing order.1 <= k <= 106
774. Minimize Max Distance to Gas Station:
The Essence:
Es gibt zuerst einen maximalen Abstand zwischen zwei Stellen. Wenn man in die Mitte dieser Stellen eine neue Stelle baut, dann gibt es irgendwo zwei andere Stellen, die den neuen maximalen Abstand besitzen, wobei diese Stellen sogar die vorherigen zwei Stellen sein können. Der maximale Abstand wird also in jedem Stellenbau verändert und man muss dazu auf eine effiziente Weise reagieren.
Details:
Die einfachste Idee ist eine Prioritätsschlange zu verwenden, die den aktuellen maximalen Abstand irgendwie liefern kann. Man kann außerdem binäre Suche verwenden. Dabei kann durch Versuch finden, welchen Abstand k neue Stellen am höchsten liefern.
Default Code:
Last updated