【每日一A】2015NOIP真题 （二分+贪心） python
题目概述
在起点和终点之间有n个石头，移除某些（不超过m个）石头后，让石头间的距离最大。
求石头间的最短距离d的最大值
跳石头
点此跳转 https://www.lanqiao.cn/problems/364/learning/?page=1&first_category_id=1&status=2&sort=difficulty&asc=0
思路分析:
最小值最大化想到二分答案法：
二分法确定d的值
贪心筛选石头
题解：
def check(x):
cnt = 0
last_idx = 0
for i in d:
if i - last_idx < x:
cnt += 1
else:
last_idx = i
if l - last_idx < x:
cnt += 1
return cnt <= m
l, n, m = map(int, input().split())
d = []
for _ in range(n):
d.append(int(input()))
left, right = 1, l
ans = -1
while left <= right:
mid = (left + right) // 2
if check(mid):
ans = mid
left = mid + 1
else:
right = mid - 1
print(ans)
END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢