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

Question

问题陈述: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;
}

谢谢!

Answer 1

首先，当您对数字进行排序时，您是在正确的轨道上，但是您的算法的复杂度是 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 ，它在 - 符号和 1 右侧出现 2 次> 时间在左边，所以我们得到 (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) 时间。你有你的答案。如果您不理解此答案的任何部分，请告诉我。