概要

各花壇の水量 \(A_i\) に対して「1リットル追加（1円）」だけが許されるとき、全ての水量を同じにするための最小費用を求めます。

考察

この操作では水を「減らす」ことができず、「増やす」ことしかできません。
したがって、最終的に全ての花壇の水量を同じ値 \(X\) に揃えるには、必ず \(X \ge \max(A_i)\) を満たす必要があります（最大値の花壇を減らせないため）。

ここで、目標値を \(X\) とすると必要な追加量（費用）は - 花壇 \(i\) に対して \(X - A_i\) リットル - 合計で \(\sum_{i=1}^{N} (X - A_i)\) 円 です。

この式は \(X\) が大きくなるほど単調に増加します（\(X\) を 1 増やすと全花壇で合計 \(N\) だけ増える）。
よって最小になるのは、条件を満たす最小の \(X\)、つまり - \(X = \max(A_i)\) のときです。

具体例：\(A=[2,5,4]\) のとき、\(\max(A)=5\)。
\(X=5\) に揃えるには \((5-2)+(5-5)+(5-4)=3+0+1=4\) 円。
\(X=6\) にすると \((6-2)+(6-5)+(6-4)=4+1+2=7\) 円で増えてしまい、最小ではありません。

素朴に「1リットルずつ追加する操作」を愚直にシミュレーションすると、差が最大で \(10^9\) あり得るため現実的な時間で終わりません（TLEの原因）。
必要なのは操作の回数そのものを数えるのではなく、差分の合計を一気に計算することです。

アルゴリズム

1. 配列 \(A\) の最大値 \(mx=\max(A)\) を求める。
2. 答えを \(\sum_{i=1}^{N} (mx - A_i)\) として計算する。
3. その合計を出力する。

計算量

• 時間計算量: \(O(N)\)（最大値の計算と合計計算）
• 空間計算量: \(O(1)\)（入力配列を除く追加領域）

実装のポイント

• 答えは最大で \(N \times (10^9-1)\) 程度になり得るので、言語によっては 64bit 整数型を使う必要があります（Python は自動で多倍長整数なので安心）。

• 入力が大きいので、Python では sys.stdin.readline を使うと安定します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    mx = max(A)
    ans = sum(mx - a for a in A)
    print(ans)

if __name__ == "__main__":
    main()

---

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