Overview

This problem asks for the minimum number of operations required to make \(N\) sticks the same length using only “shortening operations.”

Analysis

Key Insight

The key point of this problem is the constraint that “sticks can only be shortened.”

Since sticks cannot be lengthened, the target length \(T\) must be less than or equal to the length of the shortest stick.

How Should We Determine the Target Length?

Let’s consider a concrete example. If the stick lengths are \([5, 3, 7]\):

• If target is \(3\): \((5-3) + (3-3) + (7-3) = 2 + 0 + 4 = 6\) operations
• If target is \(2\): \((5-2) + (3-2) + (7-2) = 3 + 1 + 5 = 9\) operations
• If target is \(1\): \((5-1) + (3-1) + (7-1) = 4 + 2 + 6 = 12\) operations

If we set the target smaller than the minimum value \(3\), additional operations are required for all sticks, which increases the total number of operations.

Conclusion

Setting the target length to the minimum stick length \(\min(A)\) is optimal.

If we set it larger, we cannot match the minimum stick, and if we set it smaller, unnecessary operations increase.

Algorithm

1. Find the minimum value \(M = \min(A)\) of array \(A\)
2. For each stick, calculate \((A_i - M)\) and find the total sum
3. The sum is the answer

Expressed mathematically: $\(\text{Answer} = \sum_{i=1}^{N} (A_i - M) = \sum_{i=1}^{N} A_i - N \times M\)$

Complexity

• Time Complexity: \(O(N)\)
  • \(O(N)\) for finding the minimum value
  • \(O(N)\) for calculating the sum
• Space Complexity: \(O(N)\)
  • \(O(N)\) for storing array \(A\)

Implementation Notes

• Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total number of operations can be approximately \(2 \times 10^{14}\)
• In Python, there is no need to worry about integer overflow, but in C++ and similar languages, you need to use the long long type
• Using sum() and min() allows for a simple implementation

# Core part
min_length = min(a)  # Target length
total_operations = sum(x - min_length for x in a)  # Total number of operations

Source Code

n = int(input())
a = list(map(int, input().split()))

# It is optimal to make all sticks the minimum length
# Because sticks can only be shortened,
# we cannot make them longer than the minimum stick
# Also, making them shorter than the minimum stick requires extra operations

min_length = min(a)
total_operations = sum(x - min_length for x in a)
print(total_operations)

---

This editorial was generated by claude4.5opus.