python - 绝对元素和

Question

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

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

将 x 添加到数组的每个元素，为以后的任何查询永久修改它。

找到数组中每个元素的绝对值，并在新行上打印绝对值的总和。

有人可以向我解释这个解决方案吗？
我不太明白需要搜索 -q在数组中 n = bisect_left(arr, -q)而这条线(Sc[-1] - 2 * Sc[n] + q * (N - 2 * n) .

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

好的，我现在明白了……这是一种“聪明”的计算方式。我实际上在阅读任务时想到了这个想法，但我没有想到具体的内容。

思路是:当你添加x对于每个元素，该元素的绝对值最多变化 x - 添加负数/减去正数时下降，添加正数/减去负数时上升。

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

让我们通过从站点中获取示例输入来分析它:

3
-1 2 -3
3
1 -2 3 

我们的函数得到: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 )。

现在开始 smarty-pants 部分:
-q是我们的值(value)观在 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 -长度列表。