绝对元素和

Question

我试图在 Hackerrank 上解决这个问题。 https://www.hackerrank.com/challenges/playing-with-numbers/problem

给定一个整数数组，您必须回答一些问题。每个查询由一个整数 x 组成，并按如下方式执行：

将 x 添加到数组的每个元素，为将来的任何查询永久修改它。
求出数组中每个元素的绝对值，并在新行上打印绝对值之和。

谁能给我解释一下这个解决方案？
我不太明白需要在数组 n = bisect_left(arr, -q) 和这一行 (Sc[-1] - 2 * Sc[n] + q * (N - 2 * n) 中搜索 -q。

from bisect import bisect_left
def playingWithNumbers(arr, queries):
    N = len(arr)
    res = []

    # Calculate cummulative sum of arr
    arr = sorted(arr)
    Sc = [0]
    for x in arr:
        Sc.append(x+Sc[-1])

    q = 0
    for x in queries:
        q += x
        n = bisect_left(arr, -q)
        res.append((Sc[-1] - 2 * Sc[n] + q * (N - 2 * n)))
    return res

谢谢

Answer 1

it's actually one of the solutions from the leaderboard. I tried running this code, but didn't fully understand why they used those terms and the idea of the code

好的，我现在明白了...这是一种 "smartass" 的计算方式。我其实在看任务的时候就想过这个想法，但是没有想到具体的。

想法是：当你向每个元素添加 x 时，该元素的绝对值最多变化 x - 当你从正数添加到 negative/subtract 时下降，当你添加时上升从负数加到 positive/subtracts。

拥有排序列表的累加和让您不必每次都遍历列表并添加和求和，而只需计算值。

让我们通过从站点输入的示例来分析它：

我们的函数得到：arr = [-1, 2, -3]; queries = [1, -2, 3]

排序为 arr = [-3, -1, 2] 后（假设这些是 a,b,c - 字母更能解释 为什么 这行得通）我们得到我们的累计总和 Sc = [0, -3, -4, -2] (0, a, a+b, a+b+c).

现在开始聪明裤部分：

-q 是我们的值在 arr 中翻转的地方 - 也就是说，添加 q 会超过 0，使绝对值上升，而不是下降

让我们一一翻译res.append((Sc[-1] - 2 * Sc[n] + q * (N - 2 * n)))：

Sc[-1]是总和(a+b+c)
让我们先来看 q*N，它是将 q（到此为止的所有 x 值）添加到每个元素时总和的变化方式
让我们把 - 2 * Sc[n] 和 q * (-2*n) 放在一起： -2 * (Sc[n] + q*n) - 这是我提到的转折点 - 如果我们有一个负数（我们查了 -q，但是我们给它加上q），neg - 2*abs(neg) = abs(neg)，我们用Sc和*n把所有的负值都翻过来。

这个解决方案的复杂性是 O(max(n,m)*logn) - 因为排序。累加和的东西是O(n)，智能循环是O(m*logn)（二分法是O(logn)，我在评论里忘记了）

更改列表中的值的朴素方法将 O(n*m) - m 次遍历 n-length 列表。

绝对元素和

Absolute Elements Sums

python

algorithm

search

binary-search

bisect