I'm working on this problem, and any advice on performance improvement, bugs or code style issues are appreciated.
There are N gas stations on a straight, M kilo-meters long highway. The i-th gas station is Ai kilometers away from the beginning of the highway. (It is guaranteed that there is one gas station at each end of the highway.)
Now the mayor can build K more gas stations. He wants to minimize the maximum distance between two adjacent gas station. Can you help him?
The first line contains 3 integer N, M, k. (2 <= N <= 1000, 1 <= M, K <= 100000)
The second line contains N integer, A1, A2, ... AN. (0 = A1 <= A2 <= ... <= AN = M)
The minimized maximum distance rounded to one decimal place.
3 10 2 0 2 10
My major ideas are:
- Calculate lower and upper bound of gas station distance (lower bound 1, higher bound is current max distance between two existing gas stations)
- Do a binary search for lower bound and higher bound, to see if we can fit with k gas stations
- If we can fit, then try to lower higher bound of binary search
- If we cannot fit, then try to higher lower bound of binary search
- At the end, the number is minimal of max distance between gas stations
- Since it requires one decimal place, I +/- 0.1 other than +/- 1
def max_gas_distance(distances, k): max_distance = 0 for i, v in enumerate(distances): if i > 0: max_distance = max(max_distance, v - distances[i-1]) # final result between 1 and max_distance l = 1.0 h = max_distance while l <= h: mid = l + (h-l)/2.0 if valid(distances, mid, k): h = mid - 0.1 else: l = mid + 0.1 return l def valid(distances, mid, k): additional_gas_station = 0 for i,v in enumerate(distances): if i > 0 and v - distances[i-1] > mid: additional_gas_station += (v - distances[i-1]) / mid if additional_gas_station >= k+1: return False return True if __name__ == "__main__": existing_gas_stations = [0,2,10] k = 2.0 print max_gas_distance(existing_gas_stations, k)