最佳植树距离

本文主要是介绍最佳植树距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定n个坐标点位置，这些位置可以植树，有m棵树，求把m棵树都种下并且相邻树尽可能距离远时，相邻的树的距离的最小值。

输入

第一行n代表有n个坐标
第二行有n个数，用空格隔开，代表n个坐标
第三行m代表m棵树

输出

一个数，代表相邻的树的距离的最小值

思路

1. 相邻树的距离的取值范围是【1，pos[n-1]】
2. 题目的解就在这个范围里面，朴素的办法，从pos[n-1]一直往1的方向尝试，当有符合条件的就停止，当下的值就是解。更快的方法是用二分法来确定这个值。朴素的办法可能会超时，没试过。
3. 如果用朴素的办法，check 函数是要求出当相邻两棵树的距离是大于等于dist时能否种得下大于等于m棵树。二分法的的check 函数也是这样设计。dist 是当下枚举到的相邻两棵树的距离。check 前先对pos 按从小到大排序会更好处理。

代码

二分法版本

import sys n,m = None, None
pos = None # lst
cnt = 0
ans = None
for line in sys.stdin:a = line.split()if cnt == 0:n = int(a[0])elif cnt == 1:pos = aelif cnt == 2:m = int(a[0])breakcnt += 1
pos = [int(e) for e in pos]
pos = sorted(pos)
# left, right = pos[0], pos[n-1] # 这不对
left, right = 1, pos[n-1]-pos[0] # left right 决定解的范围，解的范围是[1, pos[n-1]-pos[0]]
mid = (left+right) >> 1
dis = mid 
cur_idx = pos[0]
def check(dis, pos, n, m):cnt = 1cur_idx = pos[0]for i in range(1, n):if pos[i]- cur_idx >= dis:cnt += 1cur_idx = pos[i]if cnt >= m:return True else:return Falsewhile left <= right:if check(dis, pos, n, m):# dis 是可能的解ans = dis# dis 太小left = mid + 1else:# dis 不是可能的解# dis 太大right = mid -1mid = (left+right) >> 1dis = mid print(ans)

同类型题目

LeetCode 1552 两球之间的磁力

这篇关于最佳植树距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---