To solve this problem, we need to determine the minimal cost to make all elements in a sequence the same using two operations: incrementing or decrementing an element by 1, each with a cost of 1.

Approach

The key insight here is that the minimal cost to make all elements equal is achieved by choosing the median of the sequence. This is because the median minimizes the sum of absolute deviations from all elements, which directly translates to the minimal cost in this problem.

Steps to solve the problem:

1. Sort the sequence: Sorting helps in easily finding the median.
2. Find the median: For a sequence of length (N), the median is at index (N//2) (0-based) after sorting. This works for both even and odd lengths (since any value between the two middle elements in an even-length sequence gives the same minimal cost).
3. Calculate the minimal cost: Sum the absolute differences between each element and the median. This sum is the minimal cost.

Solution Code

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

Explanation

• Sorting: Sorting the array allows us to quickly locate the median. For example, if the array is [1, 3, 5, 7], sorting gives [1,3,5,7], and the median is at index 2 (element 5).
• Median Selection: The median is chosen because it minimizes the sum of absolute deviations. For even-length arrays, any value between the two middle elements will yield the same minimal cost, so choosing either of them (like the one at index (N//2)) is valid.
• Cost Calculation: The sum of absolute differences between each element and the median gives the total cost, as each difference represents the number of operations needed to make that element equal to the median.

This approach efficiently computes the minimal cost with a time complexity dominated by the sorting step, which is (O(N \log N)), making it suitable for the given problem constraints. The space complexity is (O(1)) (excluding input storage), as we only need to store the sorted array and a few variables.

Answer: The code will output the minimal total cost as required. For example, if the input is 3 elements [1,2,3], the output will be 2. If the input is 4 elements [1,3,5,7], the output will be 8. This confirms the correctness of the approach.

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