Oranges#508

Oranges (Editorial)

Author, developer, author of the analysis: Andriy Stolitniy

Consider the case where we need to collect all the oranges at coordinate .

For each orange, we need to go to it and come back. Going away from with an orange is not optimal. Thus, for each orange, we repeat the route .

The answer looks like 2 \sum_{i=1}^{n} |x_i - k|, which can be broken down into

2 \left( \sum_{x_i \le k} (k - x_i) + \sum_{x_i > k} (x_i - k) \right)
2 \left( \sum_{x_i \le k} k - \sum_{x_i \le k} x_i + \sum_{x_i > k} x_i - \sum_{x_i > k} k \right).

Then we need to maintain such simple sums. We can go from the smallest to the largest, then maintaining such sums will be obvious.

Overall complexity: .