绝对元素求和

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

实际上是排行榜中的解决方案之一。我尝试运行此代码，但不完全理解为什么他们使用这些术语和代码思想

[好，我现在看到了……这是一种计算方式，它是“聪明的”。当我阅读任务时，我实际上想到了这个想法，但是我没有想到细节。

[想法是：当您向每个元素添加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）。

现在开始启动智能裤部分：

[-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（到此为止的所有x值）时总和的变化方式
3. 让我们一起考虑- 2 * Sc[n]和q * (-2*n)：-2 * (Sc[n] + q*n)-这是我提到的营业额点-如果我们有一个负数（我们查询了-q，但我们向其添加了q），[ C0]，我们使用neg - 2*abs(neg) = abs(neg)和Sc翻转所有负值。

---

此解决方案的复杂度为*n-由于排序。累积总和为O(max(n,m)*logn)，智能循环为O(n)（二等分为O(m*logn)，我在注释中忘记了它。）

更改列表中值的简单方法将是O(logn)-O(n*m)次遍历m长度列表。