No.3268 As Seen in Toasters
Problem Statement
For $2$ integers $x, y$, define $f(x,y)$ as follows.
- If $x < 0$ and $y < 0$, then $f(x,y) = -x-y$,
- otherwise, $f(x,y) = |x-y|$.
You are given an integer sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$. You may rearrange the elements of $A$ freely. Find the minimum possible value of $\displaystyle \sum_{i=1}^{N-1} f(A_i, A_{i+1})$.
Input
$N$ $A_1\ A_2\ \dots\ A_N$
- All inputs are integers.
- $2 \le N \le 2 \times 10^5$
- $-10^9 \le A_i \le 10^9$
Output
Output the minimum possible value of $\displaystyle \sum_{i=1}^{N-1} f(A_i, A_{i+1})$.
Sample
Sample 1
Input
3 -1 -3 4
Output
9
For example, rearranging into the order $(4,-1,-3)$ achieves the minimum value $9$.
- $f(4,-1) = |4 - (-1)| = 5$.
- $f(-1,-3) = - (-1) - (-3) = 4$.
Sample 2
Input
6 1 1 0 0 -1 -1
Output
4
For example, rearranging into the order $(-1,-1,0,0,1,1)$ achieves the minimum value $4$.
Sample 3
Input
9 117 96 102 55 -104 -123 -108 79 -131
Output
912
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
apricity