我想要实现的目标是不断向集合中添加更多值，并使它们尽可能远离彼此。我敢肯定肯定有几种算法可以解决这个问题，但我可能只是没有使用正确的术语进行搜索。如果有人能给我指出一个解决方案(不需要是一个特别有效的解决方案)那就太好了。
实际上，给定一组值 S，在 Min-Max 范围内，我需要在相同范围内计算一个新值 V，以使 V 与 S 中所有值之间的距离之和最大化。
最佳答案
很容易证明 V 的可能候选值要么是 S 的现有值，要么是最小值/最大值。证明:令S_1, S_2, ..., S_n 为S 的排序序列，包括最小值和最大值。如果你选择S_i < V < S_{i+1}，那么距离的总和可以用V = S_i或V = S_{i+1}来实现，这取决于左边和右边的点数.
这个观察产生了一个 O(n^2) 算法，它只检查 S 中的每个潜在候选者。它可以通过预先计算前缀和来计算 O(1) 中每个元素的距离总和来改进到 O(n) .
一般来说，由于每个元素对可能值的域贡献两个线性成本函数，所以这个问题可以在每个查询的 O(log n) 内解决。您只需要一个可以维护线性函数段列表并返回具有最大和的点的数据结构。具有一些巧妙的扩充和惰性更新的平衡二叉搜索树可以解决这个问题。这是否有必要当然取决于元素的数量和您希望执行的查询的数量。
关于algorithm - 计算距值集最大距离处的值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31559758/