7511: [CSES Problem Set] Stick Lengths
[Creator : ]
Description
There are $n$ sticks with some lengths. Your task is to modify the sticks so that each stick has the same length.
You can either lengthen and shorten each stick. Both operations cost $x$ where $x$ is the difference between the new and original length.
What is the minimum total cost?
You can either lengthen and shorten each stick. Both operations cost $x$ where $x$ is the difference between the new and original length.
What is the minimum total cost?
Input
The first input line contains an integer $n$: the number of sticks.
Then there are nn integers: $p_1,p_2,…,p_n$: the lengths of the sticks.
Then there are nn integers: $p_1,p_2,…,p_n$: the lengths of the sticks.
Output
Print one integer: the minimum total cost.
Constraints
$1≤n≤2⋅10^5$
$1≤p_i≤10^9$
$1≤p_i≤10^9$
Sample 1 Input
5
2 3 1 5 2
Sample 1 Output
5
将所有木棍的长度变为 $1$。这样我们需要的代价就是 $(2-1)+(3-1)+(1-1)+(5-1)+(2-1)=8$。
将所有木棍的长度变为 $2$。这样我们需要的代价就是 $(2-2)+(3-2)+(2-1)+(5-2)+(2-2)=5$。
将所有木棍的长度变为 $3$。这样我们需要的代价就是 $(3-2)+(3-3)+(3-1)+(5-3)+(3-2)=6$。
将所有木棍的长度变为 $4$。这样我们需要的代价就是 $(4-2)+(4-3)+(4-1)+(5-4)+(4-2)=9$。
将所有木棍的长度变为 $5$。这样我们需要的代价就是 $(5-2)+(5-2)+(5-1)+(5-5)+(5-2)=12$。
因此最小的代价是 $5$。
将所有木棍的长度变为 $2$。这样我们需要的代价就是 $(2-2)+(3-2)+(2-1)+(5-2)+(2-2)=5$。
将所有木棍的长度变为 $3$。这样我们需要的代价就是 $(3-2)+(3-3)+(3-1)+(5-3)+(3-2)=6$。
将所有木棍的长度变为 $4$。这样我们需要的代价就是 $(4-2)+(4-3)+(4-1)+(5-4)+(4-2)=9$。
将所有木棍的长度变为 $5$。这样我们需要的代价就是 $(5-2)+(5-2)+(5-1)+(5-5)+(5-2)=12$。
因此最小的代价是 $5$。
Sample 2 Input
3
100 100 100
Sample 2 Output
0