如何找到最小 L 使得长度为 L 的 k 个给定线段可以覆盖 n 个给定点？
How to find minimum L such that k given segments with length L could cover n given points?
x轴上有n个点，每个点的整数坐标在[0, n^3范围内
].我们可以用 k 段覆盖这些点，每段长度为 L（一个段可以覆盖其中的所有点，包括端点）。 给定k和n，如何在O(nlogn)时间内找到最小的L？
我以为if n<=k, then L ->0, 但是当n>k时，事情就开始复杂了，希望你能帮帮我.
首先，对 L 进行二分查找。假设有一个魔术函数 check(L) returns 我们是否可以用长度 L 的段覆盖点，我们使用二进制搜索找到最小值 L 使得 check(L) returns 正确。
那么，让我们来实现那个神奇的功能吧。我们可以贪婪地放置我们的线段：找到最左边未被覆盖的点，并放置一个线段，使其左端点位于该点。重复此 k 次，并检查是否所有 n 个点都已覆盖。
二分搜索调用 check(L) O(log n) 次，如果我们有点的顺序列表（只需从左到对），总共是 O(n log n)。由于点列表不变，我们可以对列表进行预排序，这也需要 O(n log n) 时间。所以这个算法的时间复杂度是O(n log n).
x轴上有n个点，每个点的整数坐标在[0, n^3范围内 ].我们可以用 k 段覆盖这些点，每段长度为 L（一个段可以覆盖其中的所有点，包括端点）。 给定k和n，如何在O(nlogn)时间内找到最小的L？
我以为if n<=k, then L ->0, 但是当n>k时，事情就开始复杂了，希望你能帮帮我.
首先，对 L 进行二分查找。假设有一个魔术函数 check(L) returns 我们是否可以用长度 L 的段覆盖点，我们使用二进制搜索找到最小值 L 使得 check(L) returns 正确。
那么，让我们来实现那个神奇的功能吧。我们可以贪婪地放置我们的线段：找到最左边未被覆盖的点，并放置一个线段，使其左端点位于该点。重复此 k 次，并检查是否所有 n 个点都已覆盖。
二分搜索调用 check(L) O(log n) 次，如果我们有点的顺序列表（只需从左到对），总共是 O(n log n)。由于点列表不变，我们可以对列表进行预排序，这也需要 O(n log n) 时间。所以这个算法的时间复杂度是O(n log n).