一个数与一个数组中的数字之差的总和

Question

这是我的问题。 给定一个整数数组和另一个整数k，找出该数组中每个元素与k的差异的总和。

例如，如果数组是2, 4, 6, 8, 10，而k是3。

Sum of difference
= abs(2 - 3) + abs(4-3) + abs(6 - 3) + abs(8 - 3) + abs(10 - 3)
= 1 + 1 + 3 + 5 + 7
= 17

该数组始终保持不变，最多可包含100,000个元素，并且将有100,000个不同的k值需要测试。k可能是数组的一个元素，也可能不是。必须在1秒内或约100M操作内完成此操作。如何实现？

- Mohideen Imran Khan

---

你的意思是绝对值差的总和。提示：将输入分成小于k和大于等于k的数字有助于解决问题吗？ - j_random_hacker

你将要处理的数据集有什么假设吗？（例如，你展示的示例集在每个索引处增加2） - sherrellbc

因为您必须至少对数据进行一次遍历，所以O(logn)或O(1)的解决方案是不可行的。 - Alexander Gessler

我刚刚看到所需的时间复杂度是o(N)（O(log N)或O(1)）：这是不可能的，除非输入有其他限制，你没有告诉我们。查看每个元素需要Omega(N)时间，并且您必须查看每个元素才能获得正确的答案！ - j_random_hacker

Answer 1

如果您添加一个预处理步骤，成本为O(N * log N)，则可以在O(log N)中运行多个绝对差值查询。

对数组进行排序，然后对数组中的每个项存储所有小于或等于相应项的数字的总和。这可以在O(N * log N)内完成。现在您有一对看起来像这样的数组：

2   4   6   8  10 // <<== Original data
2   6  12  20  30 // <<== Partial sums

此外，将数组中所有数字的总和T存储起来。

现在，你可以通过在原始数组上运行二进制搜索，并使用部分和数组中的和来计算答案来得到绝对差的总和：从目标k左侧的所有数字之和中减去目标左侧数字的个数乘以k，再从右侧数字的个数中减去k的个数，并将两个数字相加。右侧数字的部分和可以通过从总和T中减去左侧部分和来计算。

对于k=3，二进制搜索将使你到达位置1。

• 左侧部分和为2
• 左侧数字个数为1
• 右侧部分和为（30-2）=28
• 右侧数字个数为4
• 你计算出(1*3-2) + (28-4*3) = 1 + 16 = 17

- Sergey Kalinichenko

Answer 2

首先对数组进行排序，然后计算一个数组来存储结果排序数组的前缀和。我们将这个数组表示为p，你可以在线性时间内计算出p[i] = a[0] + a[1] + ... a[i]。现在有了这个数组，你可以用恒定的复杂度回答问题：元素a[x]+a[x+1]+...+a[y]（即索引从x到y）的和是多少。要做到这一点，只需计算p[y]-p[x-1]（当x为1时要特别注意）。

现在回答“什么是与k的绝对差的总和”这种类型的查询，我们将问题分为两部分——大于k的数字和小于k的数字的总和。为了计算这些值，执行二分搜索以找到排序后a中k的位置（记为idx），并计算idx之前（记为s）和之后（记为S）a中的值的总和。现在，绝对差的总和与k是idx * k - s + S - (a.length - idx) * k。当然，这是伪代码，我所说的a.length是a中的元素数量。

在进行线性对数预处理之后，您将能够使用O(log(n))回答查询。请注意，这种方法只有在您计划执行多个查询时才有意义。如果您只打算执行单个查询，则不可能比O(n)更快。

- Ivaylo Strandjev

---

但是对数组进行排序会破坏（不可能的）复杂度要求。 - juanchopanza

正如我所说，只有在存在多个查询时，这种方法才有意义。如果只有一个查询，我们无法改善O(n)。我的方法将轻松适应时间限制。这听起来像是一个竞赛问题，我相信这是预期的解决方案。 - Ivaylo Strandjev

Answer 3

我只是在"比赛C++"中实现了dasblinkenlight的解决方案：

它完全按照他所说的做。读取值，排序，将累积和存储在V[i].second中，但这里V[i]是直到i-1的累积和（为简化算法）。它还在V[n]中存储一个哨兵，以处理查询大于max(V)的情况。

然后，对于每个查询，二分搜索该值。在这种情况下，V[a].second是小于query的值的总和，V[n].second-V[a].second是大于它的值的总和。

#include<iostream>
#include<algorithm>
#define pii pair<int, int>
using namespace std;

pii V[100001];

int main() {
    int n;

    while(cin >> n) {
        for(int i=0; i<n; i++)
            cin >> V[i].first;

        sort(V, V+n);
        V[0].second = 0;

        for(int i=1; i<=n; i++) 
            V[i].second = V[i-1].first + V[i-1].second;

        int k; cin >> k;
        for(int i=0; i<k; i++) {
            int query; cin >> query;
            pii* res = upper_bound(V, V+n, pii(query, 0));

            int a = res-V, b=n-(res-V);

            int left = query*a-V[a].second;
            int right = V[n].second-V[a].second-query*b;

            cout << left+right << endl;
        }

    }
}

它假定有一个格式类似于这样的文件：

5
10 2 8 4 6
2
3 5

然后，对于每个查询，它的回答如下：

17
13

- Juan Lopes