绝对元素求和 [英] Absolute Elements Sums

问题描述

我正在尝试在Hackerrank上解决此问题. https://www.hackerrank.com/challenges/playing-with-numbers/问题

I was trying to solve this problem on Hackerrank. https://www.hackerrank.com/challenges/playing-with-numbers/problem

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

Given an array of integers, you must answer a number of queries. Each query consists of a single integer, x, and is performed as follows:

• 将x添加到数组的每个元素，为以后的任何查询永久修改它.
• 找到数组中每个元素的绝对值，并将绝对值的总和打印在新行上.

有人可以向我解释此解决方案吗?
我不太了解在数组 n = bisect_left(arr，-q)和此行(Sc [-1]-2 * Sc [n] + q *(N-2 * n).

Can someone explain this solution to me?
I didn't quite understand the need to search for -q in the array n = bisect_left(arr, -q) and this line (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

谢谢

推荐答案

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

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

好的，我现在看到了……这是一种计算的聪明方法".当我阅读任务时，我实际上想到了这个主意，但是我没有想到细节.

Okay, I see this now... It's a "smartass" way of calculating it. I actually thought about this idea when I read the task but I didn't thought of the specifics.

想法是:当您向每个元素添加 x 时，该元素的绝对值最多变化 x -当您添加负数/减去正数时会下降，上升当您添加正数/减去负数时.

Idea is: When you add x to each element, that element's absolute value changes by at most x - drops when you add to negative/subtract from positive, rises when you add to positive/subtracts from negative.

拥有已排序列表的累积总和，您不必每次都遍历该列表并进行相加和求和，而只需计算值即可.

Having a cumulative sum of a sorted list allows you to not go through the list each time and add, and sum, but to just calculate the value.

让我们通过从站点输入示例进行分析:

Let's analyse it by taking the example input from the site:

3
-1 2 -3
3
1 -2 3 

我们的函数得到: arr = [-1，2，-3];查询= [1、2、3]

排序为 arr = [-3，-1，2] 后(假设它们是 a，b，c -字母可以更好地解释为什么有效)，我们得到了累加和 Sc = [0，-3，-4，-2] ( 0，a，a + b，a + b +c ).

After sorting into arr = [-3, -1, 2] (let's say those are a,b,c - letters are better at explaining why this works) we get our cumulative sum Sc = [0, -3, -4, -2] (0, a, a+b, a+b+c).

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

Now starts the smarty-pants part:

-q 是我们的值在 arr 中翻转的位置-也就是说，添加 q 将超过0，从而使绝对价值上升，而不是下降

-q is where our values turn over in the arr - that is, where adding q would go over 0, making the absolute value rise, instead of drop

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

Let's translate this res.append((Sc[-1] - 2 * Sc[n] + q * (N - 2 * n))) one-by-one:

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 )， neg-2 * abs(neg)= abs(neg)，我们使用 Sc 和 * n 翻转所有负值.

1. Sc[-1] is the sum (a+b+c)
2. let's take q*N first, it's how the whole sum changed when adding q (all x values up to this point) to each element
3. Let's take - 2 * Sc[n] and q * (-2*n) together: -2 * (Sc[n] + q*n) - this is the turnover point I mentioned - if we have a negative number (we looked up -q, but we add q to it), neg - 2*abs(neg) = abs(neg), we use Sc and *n to turn over all the negative values.

---

此解决方案的复杂度为 O(max(n，m)* logn)-由于排序.累积总和为 O(n)，智能循环为 O(m * logn)(二等分为 O(logn)，I在评论中忘了它.)

---

This solution's complexity is O(max(n,m)*logn) - because of the sorting. The cumulative sum thing is O(n), the smart loop is O(m*logn) (bisection is O(logn), I forgot it in the comment).

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

Naive method with changing the values in the list would be O(n*m) - m times going through n-length list.

这篇关于绝对元素求和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！