绝对元素和

我试图在 Hackerrank 上解决这个问题。https://www.hackerrank.com/challenges/playing-with-numbers/problem 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

谢谢

它实际上是排行榜的解决方案之一。我尝试运行这段代码，但没有完全理解他们为什么使用这些术语以及代码的想法

好吧，我现在明白了……这是一种“聪明”的计算方式。其实我在看任务的时候也想过这个想法，但是没有想到具体的细节。

想法是：当你添加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- 字母更能解释why这有效）我们得到了累计总和Sc = [0, -3, -4, -2] (0, a, a+b, a+b+c).

现在开始 smarty-pants 部分：

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

我们来翻译一下这个res.append((Sc[-1] - 2 * Sc[n] + q * (N - 2 * n)))一对一：

1. Sc[-1]是总和 (a+b+c)
2. 让我们来q*N首先，这是相加时总和的变化q (all x到此为止的值）到每个元素
3. 让我们来- 2 * Sc[n] and q * (-2*n)一起：-2 * (Sc[n] + q*n)- 这是我提到的周转点 - 如果我们有一个负数（我们查了-q，但我们添加q到它），neg - 2*abs(neg) = abs(neg)， 我们用Sc and *n翻转所有负值。

该解决方案的复杂度是O(max(n,m)*logn)- 因为排序。累计总和是O(n)，智能循环是O(m*logn)（二分法是O(logn)，我在评论中忘记了）。

更改列表中的值的简单方法是O(n*m) - m经历过的时光n-长度列表。