找到所有可能的点对之间的力总和？

Question

有n个点，每个点有两个属性：

1. 位置（从轴）

2.景点值（整数）

两点 A 和 B 之间的吸引力由下式给出：

Attraction_force(A, B) = (distance between them) * Max(Attraction_val_A, Attraction_val_B);

找出所有可能的点对之间所有力的总和？

我尝试通过计算和添加所有对之间的力

for(int i=0; i<n-1; i++) {
    for(int j=i+1; j<n; j++) {
        force += abs(P[i].pos - P[j].pos) * max(P[i].attraction_val, P[j].attraction_val);
    }
}

示例：

Points            P1 P2 P3
Points distance:  2  3  4
Attraction Val:   4  5  6

Force = abs(2 - 3) * max(4, 5) + abs(2 - 4) * max(4, 6) + abs(3 - 4) * max(5, 6) = 23

但这需要 O(n^2) 时间，我想不出进一步减少它的方法！！

Answer 1

一种算法：

O(N²)

是最优的，因为您需要所有可能对之间的实际距离。

Answer 2

解决方案：

根据吸引力值对所有点进行排序，并从吸引力最低的点开始逐一处理。
对于每个点，您必须快速计算到所有先前添加的点的距离总和。这可以使用任何在线范围总和查询问题解决方案来完成，例如线段树或 BIT。关键思想是左边的所有点实际上都没有不同，它们的坐标之和足以计算到它们的距离之和。
对于每个新添加的点，您只需将距离总和（在步骤 2 中获得）乘以点的吸引力值，然后将其添加到答案中。

我为了发明这个解决方案所做的直觉观察：

我们这里有两个 "bad" 函数（有点 "discrete"）：max 和取模（距离）。
我们可以通过对我们的点进行排序并按特定顺序处理它们来摆脱 max。
如果我们分别处理左边和右边的点，我们就可以去掉模数。
完成所有这些转换后，我们必须计算一些东西，经过一些简单的代数转换后，将其转换为在线 RSQ 问题。

找到所有可能的点对之间的力总和？

Find the summation of forces between all possible pairs of points?

c++

algorithm

mathematical-optimization