吸引力作为编码 [英] Attraction Force as coding

问题描述

在 X 轴上存在 N 个粒子，其中每个粒子都有两个与之关联的属性，即粒子的位置及其吸引值

There are N particles present on the X axis, where, each particle has two properties associated with it, i.e. the Position of the particle and its Attraction-Value

两个粒子之间的吸引力 - i 和 j 定义为：

The Attraction-Force between two particles i and j is defined as :

吸引力（i，j）=距离（i，j）× MAX（Attraction_Value [i]，Attraction_Value [j]）

由于所有这些都是直线，任何2
粒子之间的距离等于他们的位置之间的绝对差异。

Since all of them are in a straight line, distance between any 2 particles is equal to the absolute difference between their positions.

您应该计算以下内容：

ΣN-1i =1ΣNj= i + 1（吸引力（i，j））意味着

strong> Summation（i，N-1）（Attraction Of Force（i，j））的和号（j = i + 1，N）

Summation(i,N-1)Summation(j=i+1,N) of (Attraction Of Force(i,j))

限制：

1≤N≤2×10 ^ 5

1≤Alectraction-Value≤10^ 4

1≤Position≤10^ 4

示例输入：

3
1 2
2 4
3 6

示例输出：

22

我尝试过 O（n ^ 2）如下

import java.util.*;

class TestClass {

public static void main(String args[] ) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int a[]=new int[n];
    int b[]=new int[n];
    for(int i=0;i<n;i++)
    {
        a[i]=sc.nextInt();
        b[i]=sc.nextInt();
    }
    long sol=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
          sol +=Math.abs(a[i]-a[j])*(Math.max(b[i],b[j]));   
        }
    }
    System.out.println(sol);
    }

}

请让我知道，如果有任何其他优化的方法来解决这个问题。

Please let me know if there are any other optimized way to solve this problem.

任何想法将不胜感激

感谢提前

推荐答案

我认为有一个O（n log（n））算法。首先是我的符号：我们想计算

I think there is a O(n log(n)) algorithm. First here are my notations: we want to compute

S = Sum[i] Sum[j>i] abs(x[i] - x[j]) max(m[i], m[j])

这个总和，每个（无序）对 {i，j} 出现一次，在排序粒子后，我们可以假设位置 x [i] 按升序排列。通过排序群体 m [i] ，我们可以得到一个数组 r [1]，...，r [n] ，使得 m [r [i]] 按升序排列。

In this sum, every (unordered) pair {i, j} appears exactly once and upon sorting the particles we can suppose that the positions x[i] are in ascending order. By sorting the masses m[i], we can get an array r[1], ..., r[n] such that the m[r[i]] are in ascending order.

我的想法是构建一个包含粒子的平衡二叉搜索树，基于它们的位置，使得在每个子树T的根处，一个存储子树的粒子数和子树的粒子位置的总和。

My idea is to build a balanced binary search tree containing the particles, based on their positions, such that at the root of every subtree T, one stores the number of the subtree's particles and the sum of the subtree's particles positions.

有了这些数据，对于任何实数 x ， Sum [i] abs（x-x [i]） 可以在时间O（log（n））中确定。

With this data, for any real number x, the Sum[i] abs(x - x[i]) can be determined in time O(log(n)).

现在将最重的粒子排在等级 r [ n] ，它对
总和 S 的贡献是 m [r [n]] Sum [i ] abs（x [r [n]] - x [i]）。该贡献可以在时间 0（log（n））中计算。我们可以从二进制树中删除最重的粒子，或者通过在平衡树上使用标准算法，或者更简单地通过修改节点上包含的数据来消除最重的粒子。

Now taking the heaviest particle with rank r[n], its contribution to the sum S is m[r[n]] Sum[i] abs(x[r[n]] - x[i]). This contribution can be computed in time 0(log(n)). We can then remove the heaviest particle from the binary tree, either by using standard algorithms on balanced trees, or more simply by modifying the data contained on the nodes.

在一个接一个地感应最重的粒子，我们在时间 O（n log（n））中获得总和 S 。

By removing inductively the heaviest particles one after the other, we obtain the sum S in time O(n log(n)).

这篇关于吸引力作为编码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！