OD 算法题 B卷 【最佳植树距离】

最佳植树距离

• 在直线的公路上种树，给定坑位数量和位置，及需要种多少棵树苗；
• 树苗之间的最小距离是多少时，可以保证种的最均匀（树苗之间的最小距离最大）；

输入描述：
第一行坑位数量；
第二行坑位的位置；
第三行需要种植树苗的数量；
输出描述：
树苗之间的最小距离

示例1：
输入：
7
1 3 6 7 8 11 13
3
输出：
6

示例2：
输入：
8
1 3 6 7 8 11 16 13
4

输出：
5

import bisect# 输入数据
n = int(input())
pos_list = [int(x) for x in input().split(" ")]
m = int(input())def count(num):""" 统计以num为间距，在有效位置内可以种植的树的棵数 """global pos_list# 起始位置stack = [pos_list[0]]# 植树的棵数cnt = 1# 循环计算while True:# 在有序列表中插入一个值，并保证有序# 返回（相等值的）最右边插入位置的索引index = bisect.bisect(pos_list, stack.pop() + num)if index == len(pos_list):# breakstack.append(pos_list[index])cnt += 1return cntdef solve():global pos_list, m# 升序排序    pos_list.sort()# 间距的最小值与最大值left, right = 1, pos_list[-1] // (m-1)while left < right:# 取中间的间距值mid = (left + right) // 2if count(mid) >= m:# 按照当前的间距种植的树多于m， 则表示间距过小left = mid + 1else:right = midreturn leftprint(solve())