algorithm - 给定N个整数数组，如何计算C++中的差异之和？

问题陈述：https://www.codechef.com/ZCOPRAC/problems/ZCO13001
我的代码在测试用例4和5上的运行时间是2.01秒我无法找出代码的问题：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int summation(long long int a[], int n, int count)
{
    long long int sum=0;
    int i;
    if(count==n)
        return 0;
    else
    {
        for(i=count; i<n; i++)
            sum+=a[i]-a[count];

    }
    return sum+summation(a, n, count+1);
}

int main()
{
    int n, i;
    long long int sum;
    scanf("%d", &n);
    long long int a[n];

    for(i=0; i<n; i++)
        scanf("%lld", &a[i]);
    sort(a, a+n);

    sum=summation(a, n, 0);
    printf("%lld\n", sum);
    return 0;
}

谢谢！

最佳答案

首先，当你对数字排序时，你在正确的轨道上，但是你的算法的复杂性是O(n^2)。你想要的是一个O(n)算法。
我只想给你一个提示，之后你如何使用它取决于你。
让我们以您指定的站点为例，即3,10,3,5。对这些元素进行排序，得到3,3,5,10。那么，这些差异之和的具体构成要素是什么呢？它们如下-
3-3
5-3
10-3
5-3
10-3
10-5
我们的结果应该是(3-3) + (5-3) + ... + (10-5)让我们以不同的方式来处理这个表达式。
3 - 3
5 - 3
10 - 3
5 - 3
10 - 3
10 - 5
43 - 20
这是通过在-符号的左侧和右侧添加元素得到的。
现在取一个变量sum = 0。
你需要做以下观察-
从这些个体差异中可以看出，第一个3出现在-符号右侧的次数是多少？
它出现了3次，所以让我们采取sum = -3*3 = -9。
现在对于第二个3，它在2符号的右侧出现-次，在左侧出现1次，所以我们得到(1-2)*3 = -3。把这个加到sum中，我们得到-12。
同样，对于5我们在左侧有2次，在右侧有1次我们得到(2-1)*5 = 5。把这个加到sum中，我们得到-12+5 = -7。
现在对于10我们在左边有3次，即3*10次，所以sum是=-7+30 = 23这是您需要的答案。现在您需要考虑的是一个数字出现在-符号的左侧和右侧的次数。这可以在O(1)时间内完成，对于n元素需要O(n)时间。
给你答案。如果你不明白这个答案的任何部分，请告诉我。