Minimum Cost to Make All Equal
Given an array of N integers, you want to make all elements equal to some value X. The cost of changing an element a[i] to X is |a[i] - X|. You can choose any integer X to minimize the total cost, which is the sum of costs for all elements. Find this minimum total cost.
Input
The first line contains an integer N. The second line contains N space-separated integers a_1, a_2, ..., a_N.
Output
Print a single integer, the minimum total cost.
Constraints
1 <= N <= 200000. -10^9 <= a_i <= 10^9.
Example 1
3 1 2 6
5
Sorted array is [1, 2, 6]. Median is 2. Cost = |1-2| + |2-2| + |6-2| = 1 + 0 + 4 = 5.
Example 2
4 1 1 5 10
13
Sorted array is [1, 1, 5, 10]. Medians can be any value between 1 and 5. Choosing 1: Cost = |1-1|+|1-1|+|5-1|+|10-1| = 0+0+4+9 = 13. Choosing 5: Cost = |1-5|+|1-5|+|5-5|+|10-5| = 4+4+0+5 = 13. For N=4, indices are 0,1,2,3. Median elements are at index 1 (value 1) and index 2 (value 5). The minimum c
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 1 2 6
4 1 1 5 10