To solve this problem, we need to find the minimal number of operations to make all elements of a sequence equal. The allowed operations are increasing/decreasing an element by 1 (cost 1) or flipping its sign (cost C).

Approach

1. Key Insight: For each element, we have two possible values to consider: the original value or its negative (with the flip cost if we choose the negative).
2. Candidate Target Values: The optimal target value (T) to make all elements equal will likely be one of the original values or their negatives. This is because the sum of absolute differences (cost of adjusting elements to T) is minimized at the median of the candidate values.
3. Cost Calculation: For each candidate target value (T), compute the minimal cost for each element to reach T by either keeping it as is or flipping it (whichever is cheaper). Sum these minimal costs for all elements and track the minimum sum across all candidate T values.

Solution Code

n, C = map(int, input().split())
x = list(map(int, input().split()))

# Collect all candidate target values: original and flipped
candidates = set()
for num in x:
    candidates.add(num)
    candidates.add(-num)

min_total = float('inf')

for T in candidates:
    total = 0
    for num in x:
        # Cost without flipping
        cost_no_flip = abs(num - T)
        # Cost with flipping
        cost_flip = C + abs(-num - T)
        total += min(cost_no_flip, cost_flip)
    if total < min_total:
        min_total = total

print(min_total)

Explanation

1. Candidate Targets: We generate all possible target values by considering each element and its negative. This ensures we cover all potential optimal targets.
2. Cost Calculation: For each candidate target (T), we calculate the cost for each element to reach T. The cost for each element is the minimum of:
   • Adjusting the element to T without flipping (cost = absolute difference between element and T).
   • Flipping the element (cost C) and then adjusting to T (cost = absolute difference between flipped element and T).
3. Minimize Total Cost: We sum the minimal costs for all elements for each candidate T and keep track of the smallest sum, which gives the minimal number of operations needed.

This approach efficiently narrows down the possible target values and computes the minimal cost, ensuring optimal performance even for moderate-sized sequences. The complexity is O(n^2) in the worst case, which is feasible for typical problem constraints. However, for larger sequences, we could optimize using ternary search on the target value (since the cost function is unimodal), but the current approach is straightforward and works well for most cases.

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