概要

全ての棒を「伸ばさずに」同じ正の長さにそろえるとき、必要な切断回数の最小値を求める問題です。

考察

• 1回の操作でできることは「選んだ棒を \(1\) cm 短くする」だけなので、最終的な共通の長さを \(L\) とすると、必ず \(L \le A_i\)（全ての棒で） が必要です。
  つまり \(L\) は \(L \le \min(A)\) を満たす必要があります。
• また、長さ \(0\) は使えないので \(L > 0\) が必要ですが、制約より \(A_i \ge 1\) なので \(\min(A) \ge 1\)、よって \(L=\min(A)\) は必ず条件を満たします。

では、どの \(L\) を選べば切る回数（合計）が最小になるでしょうか？

• 棒 \(i\) を \(A_i\) から \(L\) にするには \(A_i - L\) 回切る必要があります。
• 合計回数は
  $\( \sum_{i=1}^{N} (A_i - L) = \left(\sum_{i=1}^{N} A_i\right) - N L \)$
• 右辺を見ると、\(L\) が大きいほど（可能な範囲で）合計回数は小さくなります。
  しかし \(L\) は最大でも \(\min(A)\) までしか取れないため、最適な \(L\) は \(L=\min(A)\) です。

素朴に「毎回一番長い棒を切る」などをシミュレーションすると、切る回数が最大で \(\sum A_i\) オーダーになり得て（\(A_i\) が \(10^9\) なので不可能）、TLE になります。
この問題は「最終的な長さは最小値に決まる」という観察で一発計算できます。

例: \(A=[5,3,7]\)
\(\min(A)=3\) にそろえるのが最善。必要回数は \((5-3)+(3-3)+(7-3)=2+0+4=6\)。
式でも \(\sum A - N\min(A)=15-3\cdot 3=6\)。

アルゴリズム

1. 配列 \(A\) の最小値 \(mn=\min(A)\) を求める
2. 配列の総和 \(total=\sum A_i\) を求める
3. 答えは
   $\( total - mn \times N \)$ を出力する

計算量

• 時間計算量: \(O(N)\)（最小値と総和を1回ずつ求める）
• 空間計算量: \(O(1)\)（入力配列を除けば定数）

実装のポイント

• \(N \le 2\times 10^5\) なので、Pythonでは sys.stdin.buffer.read() による高速入力が安全です。

• 答えは最大で \(N \times 10^9\) 程度になり得ますが、Python の整数はオーバーフローしません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:]
    mn = min(a)
    total = sum(a)
    print(total - mn * n)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。