数字与数字数组之差之和

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

数组始终保持不变，可以包含多达100000个元素，并且将有100000个不同的k值需要测试。K可能是数组的一个元素，也可能不是一个元素。这必须在1s或大约1亿次操作内完成。我怎样才能做到这一点？

Answer 1

如果添加了成本为O(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

Answer 2

首先对数组进行排序，然后计算一个数组，该数组存储结果排序数组的前缀之和。让我们来表示这个数组p，您可以用线性时间计算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(表示idx)中k的位置，并计算idx(表示s)之前的a值和idx后的值(表示S)。现在，与k的绝对差之和是idx * k - s + S - (a.length - idx)* k。当然，这是伪代码，我所说的a.length是指a中的元素数。

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

Answer 3

只是在“竞赛C++”中实现了dasblinkenlight的解决方案：

就像他说的那样。读取值，对它们进行排序，将累积和存储在Vi.second中，但这里Vi是i-1之前的累积和(以简化算法)。它还在Vn中存储一个哨兵，用于查询大于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