ID: 1075

Difficulty: 5

所属公司 : 美团

时间 :2024年8月31日

题目内容

长度无限长的公路上，小美雇佣了 $n$ 位工人来种树，每个点最多种一棵树。

从左向右数，工人所站的位置为 $a_1,a_2,...,a_n$ 。已知每位工人都会将自己所在位置的右侧一段长度的区间种满树，且每位工人的种树区间长度相同。

思路：二分

随着种树区间的增长，公路上被种上的树的数量单调不降，具有单调性，因此可以使用二分解决。

二分种树区间长度，并 $O(N)$ 扫一遍工人的种树区间，判断能否种上 $k$ 棵树，能就减少二分长度，否则增大二分长度。