论文目录链接怎么做,如何做网站导航栏的seo优化,优秀设计集锦网站,伍佰亿搜索引擎网站系统题目
给定n个坐标点位置#xff0c;这些位置可以植树#xff0c;有m棵树#xff0c;求把m棵树都种下并且相邻树尽可能距离远时#xff0c;相邻的树的距离的最小值。
输入
第一行n代表有n个坐标 第二行有n个数#xff0c;用空格隔开#xff0c;代表n个坐标 第三行m代表…题目
给定n个坐标点位置这些位置可以植树有m棵树求把m棵树都种下并且相邻树尽可能距离远时相邻的树的距离的最小值。
输入
第一行n代表有n个坐标 第二行有n个数用空格隔开代表n个坐标 第三行m代表m棵树
输出
一个数代表相邻的树的距离的最小值
思路
相邻树的距离的取值范围是【1pos[n-1]】题目的解就在这个范围里面朴素的办法从pos[n-1]一直往1的方向尝试当有符合条件的就停止当下的值就是解。更快的方法是用二分法来确定这个值。朴素的办法可能会超时没试过。如果用朴素的办法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 (leftright) 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 (leftright) 1dis mid print(ans)
同类型题目
LeetCode 1552 两球之间的磁力
