在n个可能的不同位置中，找到k个对象之间最大的最小距离是多少？

Question

什么是在n个不同可能位置中找到k个对象的最大最小距离的高效方法？

例如： N：不同位置的数量 假设 N = 5，其中 5 个位置为 {1,2,4,8,9}。

K：对象的数量，假设 k = 3

因此，最大最小距离的可能答案是：如果我们将对象放置在 {1,4,8} 或 {1,4,9}，则为 3。

- Jitendra Sarswat

---

什么是“最大最小值”？ - Ed Heal

“最大最小值”是在某个可用的k位置最终放置的物体之间的距离，以上例子中为3。例如，1和4之间的距离为3，4和8之间的距离为4。 - Jitendra Sarswat

你在Codechef比赛期间询问问题是不道德的行为。你应该尊重Codechef比赛的规则和法规。 :( http://www.codechef.com/CONI2015/problems/CN03 - user2776601

我并不打算提交这个问题。 :-) 所以没有恶意。只是为了学习目的，因为没有教程可用 :-( @NewUser - Jitendra Sarswat

但是您应该等到比赛结束几个小时后再问，比赛结束后您仍然可以询问比赛问题。 - user2776601

我投票关闭此问题，因为它不属于本网站，应该发表在https://programmers.stackexchange.com。 - Alexander Vogt

Answer 1

1. 让我们对答案进行二分搜索。

2. 对于固定的答案x，我们可以使用一个简单的线性贪心算法来检查它是否可行（选择第一个元素，然后迭代遍历数组的其余部分，如果当前元素与上一个选择的元素之间的距离大于或等于x，则将其添加）。最后，我们只需要检查选取的元素数量是否至少为k。

时间复杂度为O(n * log MAX_A)，其中MAX_A是数组中的最大元素。

以下是此算法的伪代码：

def isFeasible(positions, dist, k):
    taken = 1
    last = positions[0]
    for i = 1 ... positions.size() - 1:
        if positions[i] - last >= dist:
            taken++
            last = positions[i]
    return taken >= k

def solve(positions, k):
    low = 0 // definitely small enough
    high = maxElement(positions) - minElement(positions) + 1 // definitely too big
    while high - low > 1:
        mid = (low + high) / 2
        if isFeasible(positions, mid, k):
            low = mid
        else:
            high = mid
    return low

- kraskevich

---

我不明白如何在这里使用二分查找？ - Jitendra Sarswat

@JitendraSarswat 如果我们确定了期望的答案，就可以检查它是否可行（并且它是单调的）。因此，我们可以使用二分查找来找到最大的可行答案。 - kraskevich