加油站最大距离最小

Question

我正在研究这个问题，任何关于性能改进、bug或代码风格问题的建议都会受到欢迎。

问题

描述在一条长M公里的直公路上有N个加油站.第一个加油站离高速公路的起点有几公里远.(保证高速公路两端各有一个加油站。)现在市长可以建造更多的加油站了。他想把相邻两个加油站之间的最大距离降到最小。你能帮他吗？输入:第一行包含3个整数N，M，k。(2 <= N <= 1000，1 <= M，K <= 100000)第二行包含N个整数，A1，A2，.一个。(0 = A1 <= A2 <= . <= AN = M)输出:最小最大距离四舍五入到小数位。样本输入3 10 2 0 2 10样本输出2.7

我的主要想法是：

1. 计算加油站距离的上下界(下限1，上限是两个现有加油站之间的最大距离)
2. 对下界和上界进行二进制搜索，看看我们是否适合k个加油站。
   1. 如果我们能适应，那就尽量降低二进制搜索的上限。
   2. 如果我们不能适应，那么就尝试更高的二进制搜索下限。

3. 最后，加油站之间的最大距离最小。
4. 因为它需要小数点一位，所以i +/- 0.1 ( +/- 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)

Answer 1

Bugs/Correctness

1. 在二进制搜索中，当找到一个好值(即当有效返回true时)时，您的代码在尝试进一步优化它之前不会保存它。如果有效(距离，mid，k)：h=中间- 0.1 #，那么最好的值就丢失了。最好的办法是节省你到目前为止找到的最佳距离。如果有效(距离，mid，k)：best_so_far = mid h=MID-0.1.返回best_so_far
2. (v - distances[i-1]) / mid，如果车站之间的距离是6，mid是3，结果是2，而你只需要增加1个加油站。你真正想做的是得到distance / mid的上限，它会给出长度mid的数量，然后减去一个，得到中间的加油站数量。所以math.ceil(distance / mid) - 1。

码样式

总的来说，我认为代码非常干净，具有清晰的变量名和良好的模块化。

1. 在枚举(距离)中，每两个元素的最大距离( max_distance =0)：如果i > 0: max_distance = max( max_distance，v-max_distance一-一)，则可以用更复杂的方式写成:max_distance= max(a +b表示a，b表示zip(距离，距离1：))。
2. 方法名valid并不是真正可读的，而且变量名称mid和k也没有表现力。所以我会把它重命名为。Is_solvable(距离，distance_required，additional_stations)