在最大化最小距离的情况下放置n个点。

Question

给定距离 d（从 0 到 d），以及两个点 s 和 e，它们之间不能放置任何其他点（在 s 和 e 上放置点是可以的，但不能在它们之间放置点）。

放置 n 个点，使得每个点之间的距离尽可能大（尽量平均地分布）。

输出两点之间的最小距离。

图形表示，在黑线上放置 n 个点（这是一条一维线），使得每两个点之间的最小距离尽可能大（允许绝对误差高达 10^(-4)）。

例子：

• d=7, n=2, s=6, e=7, 输出为: 7.0000000000
• d=5, n=3, s=5, e=5, 输出为: 2.5000000006
• d=3, n=3, s=0, e=1, 输出为: 1.5000000007
• d=9, n=10, s=5, e=6, 输出为: 1.0000000001
• d=6, n=2, s=1, e=6, 输出为: 6.0000000000
• d=5, n=3, s=4, e=5, 输出为: 2.5000000006

我的方法：

我尝试分别查看间隔，将点（理想分布，lengthOfInterval/n）分布在第一个和第二个间隔（从 0 到 s 和从 e 到 d），并检查所有点数总和为 n 的分布，我会存储一个（分布，最大最小距离）对，并选择具有最大最小距离的对。我不知道如何处理 10^(-4) 的容差（这部分代码应该如何实现？），也不确定我的方法是否正确。欢迎提出任何建议。

我卡在这个问题上了:/

- PlsWork

---

我现在会采用类似的方法，但要注意间隙可能非常小。你最终会得到两个非常接近的点，因此不是均匀分布的。至于公差，它不是用来纠正作业或练习的吗？ - AxelH

请查看O(1)解决方案。 - maraca

Answer 1

您可以使用二分查找来确定可能的点之间距离（从0到d）的大小，从而得出最大的最小间隔。

要确定任何给定间隔大小的可行性，基本上是尝试从左边和右边放置点，并查看中间的间隔是否足够大：

- 确定可以放置在s左边的点数（即s / gapSize + 1）。 - 然后确定需要放置在e右边的点数（即n - s左侧的点数）。 - 再确定每个侧面将向内延伸多远。 - 检查右侧的点是否适合于间隙[e，d]，以及两边之间是否至少有gapSize差异。

代码如下：（请注意，我使用间隙数而不是点数来处理，因为它可以导致更简单的代码）

double high = d, low = 0, epsilon = 0.000001;
while (low + epsilon < high)
{
    double mid = (low + high)/2;
    int gapsOnLeft = (int)(s/mid); // gaps = points - 1
    if (gapsOnLeft + 1 > n)
        gapsOnLeft = n - 1;
    int gapsOnRight = n - gapsOnLeft - 2; // will be -1 when there's no point on the right
    double leftOffset = mid*gapsOnLeft;
    // can be > d with no point on the right, which makes the below check work correctly
    double rightOffset = d - mid*gapsOnRight;
    if (leftOffset + mid <= rightOffset && rightOffset >= e)
        low = mid;
    else
        high = mid;
}
System.out.println(low);

演示。

时间复杂度为 O(log d)。

---

你的方法存在问题，难以确定点之间应该有多大的间隔，因此你不知道在两侧应该放置多少个点才能得到最优解，并正确处理和非常接近和远离时的两种情况。请注意保留HTML标签。

- Bernhard Barker

---

请注意，对于 d=9, n=10, s=5, e=6，这将打印0.9999而不是0.8333，因为您可以在每个整数0-9上放置10个点，导致每个点之间的差异为1。不确定为什么会被认为是不正确的，或者0.83是否只是制作示例的人的打字或实现错误。 - Bernhard Barker

修复了，发现得好，我正在尝试理解你的解决方案，看起来正确！感谢你的努力 :) - PlsWork

应该把 epsilon 改成 0.0001 吗？ - PlsWork

@AnnaVopureta Epsilon 应该小于或等于 0.0001。我倾向于选择稍微更低的值，因为浮点运算是不精确的，至少在不太影响运行时间的情况下。 - Bernhard Barker

我认为复杂度是log(d/epsilon)，这仍然算作log(d)吗？ - maraca

@maraca 由于epsilon是常数，它不会影响大O复杂度。它仍然是O(log d)。 - Bernhard Barker

Answer 2

简而言之： 你的方法并不总是有效（而且你的速度也不够快），请查看第三个要点以了解有效的方法（并使用给定的10^(-4)）。

• 如果[s，e]较小且位置良好，则最佳方法只需均匀分布在整个区间上，最佳值现在为d /（n-1）。但您必须检查您的元素是否位于s和e之间。

• 如果s和e足够远，则您的方法有效。

你可以比你所建议的更快地完成它，通过在时间O(1)内寻找两个段之间的最佳分割：如果你把n1（1<=n1<=n-1）个元素放在左边，你想要最大化min(s/(n1-1), (d-e)/(n-n1-1))（其中一个量可能是+infinity，但另一个不是）。该函数的最大值是通过s/(x-1) = (d-e)/(n-x-1)计算得到的，只需计算x的相应值，其floor或ceiling即为n1的最佳值。得到的距离为best = min(s/(n1-1), (d-e)/(n-n1-1))，然后你将在左侧放置n1个点，从0开始，以best的距离分隔，右侧放置n-n1个点，从d开始向左移动，以best的距离分隔。

如果左侧最后一个点和右侧第一个点之间的距离小于最佳值，那么你会有问题，这种方法行不通。

• 复杂情况是当前两种方法失败时：孔很小且位置不好。那么可能有很多方法来解决这个问题。其中一种方法是使用二分查找来寻找两个连续点之间的最优距离。给定一个候选距离sp，在从0开始的线上以sp为间隔分布点，尽可能多地放置点，同时保持总距离小于s。在右侧进行相同的操作，同时保持大于e并在(左侧最后一个点 + sp)以上。如果成功放置了至少n个点，则sp太小。否则，它太大。

因此，您可以使用二分查找来寻找最优 sp。具体而言，从可能的区间 [max(s, d-e)/(n-1), d/(n-1)] 开始。每一步，取可能区间的中点 mid。检查真正的最优值在 mid 上方还是下方。根据您的情况，在区间 [mid, y] 或者 [x, mid] 中查找最优值。当 y-x < 10^(-4) 时停止。

实际上，这种方法也会发现前两种情况，因此您不需要实现它们，除非您需要尽可能精确地求出最优值（即在前两种情况下）。

- gdelab

---

"这些量中的一个可能是+无穷大" - 除以0是未定义的，不是无穷大。 - Bernhard Barker

@Dukeling 我知道。我的意思是，在编码时，他应该允许在一侧只放置1个元素，并将两个节点之间的距离赋值为+无穷大，以便两侧中的最小值是另一个值。无论如何，如果他不想在这种情况下获得精确的最优值，他就不需要代码的这部分。我试图解释的是，他不需要计算两侧之间的所有可能分离来找到最佳分离，这将花费O(n)的时间。 - gdelab

Answer 3

二分查找

如果已知任意一对点之间的最小距离l，那么很容易找到可以放置的点数。

如果l=d，则最多只能放置2个点。
..
...
....

因此，只需在l上进行二分查找即可。

一个简单的实现方法如下。

low,high=0.00001,d
while(high-low>eps):
    m = (low+high)/2
    if((no. of points placed s.t any pair is at most m units away) >=n):
        low=mid
    else:
        high=mid

- v78

Answer 4

这个问题相当棘手，除了简单情况（没有点落在间隙中）之外：

double dMin = d / (n - 1.0);
if (Math.ceil(e / dMin - 1) * dMin <= s)
    return dMin;

让我们继续处理边缘情况，将一个点放在一侧，其余的点放在另一侧：

dMin = Math.min((d - e) / (n - 2.0), e); // one point at 0
double dm = Math.min(s / (n - 2.0), d - s); // one point at d
if (dm > dMin) // 2nd configuration was better
    dMin = dm;

最后，对于两侧的两个或多个点：

// left : right = (x - 1) : (n - x - 1)
// left * n - left * x - left = right * x - right
// x * (left + right) = left * n - left + right
// x = (left * n - left + right) / (left + right) = (left * n) / (left + right) - 1 
int x = s * n / (d - e + s) - 1;
if (x < 2)
    x = 2;
for (int y = x; y <= x + 2 && y < n - 1; y++) {
    double dLeft = s / (y - 1.0);
    double dRight = (d - e) / (n - y - 1.0);
    dm = Math.min(dLeft, dRight);
    if (dm > e - s) { // dm bigger than gap 
        if (dLeft > dRight)
            dLeft = e / ((double) y);
        else
            dRight = (d - s) / ((double) n - y);
        dm = Math.min(dLeft, dRight);
    }
    if (dm > dMin)
        dMin = dm;
}

这将是O(1)的空间和时间复杂度，但我不能百分之百确定是否检查了所有情况。如果它有效，请告诉我。已针对所有测试用例进行了测试。以上适用于n >= 2，如果n等于2，则会被第一个检查捕获。

- maraca

---

你代码中的0.833333注释让我以为我的代码有问题，但到目前为止它还是正确的，正确答案是1.0。 - maraca