概要

与えられた \(N\) 本の棒の長さをすべて同じにして、かつその長さを \(0\) より大きく保つために必要な最小の切断回数を求めます。

考察

この問題では、すべての棒の長さを「等しく」かつ「正の値」にする必要があります。
棒を伸ばすことはできないので、最終的な共通の長さは、最も短い棒の長さ以下にする必要があります。
また、長さが \(0\) になってはいけないので、最終的な長さは少なくとも \(1\) 以上である必要があります。

ここで重要な観察があります：
最終的な長さを最も短い棒の長さに設定するのが最適です。
なぜなら、それより短くすると、さらに多くの切断が必要になり、無駄が生じるからです。

例えば、棒の長さが \([5, 3, 7]\) だったとします。
最短の長さは \(3\) なので、すべての棒を長さ \(3\) に揃えるのが最適です： - \(5 \rightarrow 3\) ：2回切る - \(3 \rightarrow 3\) ：0回切る - \(7 \rightarrow 3\) ：4回切る
合計：6回の切断が必要です。

もし最終的な長さを \(2\) にすると、合計はさらに増えてしまいます。
したがって、最終的な長さを「最小の棒の長さ」にすることが最適解となります。

アルゴリズム

1. 入力からすべての棒の長さ \(A_i\) を受け取る。
2. 最小の長さ \( \min(A) \) を求める。
3. 各棒に対し、\( A_i - \min(A) \) 回だけ切る必要がある。
4. すべての棒についてその差分を足し合わせたものが答えとなる。

つまり、求めたいのは以下の値です：

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

これはPythonのリスト内包表記やsum関数を使うことで簡単に計算できます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力を除く）

\(N\) は最大で \(2 \times 10^5\) なので、十分高速に動作します。

実装のポイント

• 入力を高速に読み込む（sys.stdin.readなど）ことで大きなテストケースにも耐えられる。
• min(A) を一度だけ求めて使い回すことで無駄な計算を避ける。
• 切断回数が非常に大きくなる可能性があるため、オーバーフローに注意（Pythonでは気にしなくてよい）。

## ソースコード

```python
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()

この解説は qwen3-coder-480b によって生成されました。