Overview

Given \(N\) sticks, find the minimum number of cuts needed to make all sticks the same length while keeping that length greater than \(0\).

Analysis

In this problem, all sticks must be made “equal” in length and that length must be “positive.” Since we cannot extend sticks, the final common length must be at most the length of the shortest stick. Also, since the length cannot be \(0\), the final length must be at least \(1\).

Here is an important observation: It is optimal to set the final length to the length of the shortest stick. This is because making it any shorter would require even more cuts, resulting in unnecessary waste.

For example, suppose the stick lengths are \([5, 3, 7]\). The shortest length is \(3\), so it is optimal to make all sticks length \(3\): - \(5 \rightarrow 3\): 2 cuts - \(3 \rightarrow 3\): 0 cuts - \(7 \rightarrow 3\): 4 cuts Total: 6 cuts needed.

If we set the final length to \(2\), the total would increase even further. Therefore, setting the final length to “the minimum stick length” gives the optimal solution.

Algorithm

1. Read all stick lengths \(A_i\) from input.
2. Find the minimum length \(\min(A)\).
3. For each stick, we need to cut exactly \(A_i - \min(A)\) times.
4. The answer is the sum of these differences across all sticks.

In other words, the value we want is:

\[ \sum_{i=1}^{N} (A_i - \min(A)) \]

This can be easily computed using Python’s list comprehension and the sum function.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Since \(N\) is at most \(2 \times 10^5\), this runs sufficiently fast.

Implementation Notes

• Use fast input reading (e.g., sys.stdin.read) to handle large test cases.

• Compute min(A) only once and reuse it to avoid unnecessary computation.

• The number of cuts can become very large, so be careful about overflow (not a concern in Python).

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    # 最小の棒の長さを取得
    min_length = min(A)
    
    # 各棒を min_length まで切るのに必要な回数の総和
    total_operations = sum(a - min_length for a in A)
    
    print(total_operations)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.