To solve this problem, we need to determine the minimal number of operations (increment or decrement by 1) required to make all elements in an array equal. The optimal target value for minimizing these operations is the median of the array, as it minimizes the sum of absolute deviations.

Approach

1. Sort the Array: The median of an array is easily found after sorting.
2. Find the Median: For an array of size n, the median is the element at index n//2 (integer division) after sorting. For even n, either middle element works since the sum of absolute differences will be the same.
3. Calculate Total Operations: Compute the sum of absolute differences between each element and the median. This sum gives the minimal number of operations needed.

Solution Code

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
median = arr[n // 2]
total = sum(abs(x - median) for x in arr)
print(total)

Explanation

• Sorting: Sorting the array allows us to quickly access the median.
• Median Selection: The median minimizes the sum of absolute deviations. For example, if the array is [1, 4, 5], the median is 4 and the sum of absolute differences is 3 + 0 + 1 = 4, which is the minimal possible.
• Sum Calculation: The sum of absolute differences between each element and the median directly gives the total number of operations needed (each difference represents the steps to adjust that element to the median).

This approach efficiently computes the result with a time complexity dominated by the sorting step, which is (O(n \log n)), making it suitable for large input sizes. The space complexity is (O(1)) (excluding input storage) since we only need to store the sorted array and a few variables.

Answer: The minimal number of operations is the sum of absolute differences between each element and the median, which is computed as shown in the code. For example, if the input is 5 and [1,3,5,7,9], the output is 12.

(\boxed{12}) (for the example mentioned) or the result from the code for any input. The code will output the correct value based on the input provided.

作者声明:本文包含人工智能生成内容。