概要

\(N\) 個の花壇の水の量を、水を足す操作のみで等しくするために必要な最小費用を求める問題です。

考察

この問題のポイントは、「水を減らすことはできず、増やすことしかできない」という点です。

すべての花壇の水の量を一致させるためには、少なくとも現在最も多くの水が入っている花壇の量（最大値）まで、他のすべての花壇の水の量を引き上げる必要があります。

もし、最大値よりもさらに多い量で揃えようとすると、すべての花壇に対して追加で水を足す必要が出てくるため、費用が余計にかかってしまいます。したがって、最小の費用で目標を達成するには、「すべての花壇の水の量を、現在の最大値に合わせる」のが最適です。

具体例で考えてみましょう。 花壇の水の量が \([2, 5, 3]\) だった場合： - 最大値は \(5\) です。 - \(1\) 番目の花壇：\(5 - 2 = 3\) リットル追加 - \(2\) 番目の花壇：\(5 - 5 = 0\) リットル追加 - \(3\) 番目の花壇：\(5 - 3 = 2\) リットル追加 - 合計費用：\(3 + 0 + 2 = 5\) 円

このように、各花壇について「最大値との差」を合計すれば答えが求まります。

アルゴリズム

1. 与えられた数列 \(A\) の中から最大値 \(M\) を見つけます。
2. 各花壇 \(A_i\) について、不足分 \(M - A_i\) を計算し、その総和を求めます。
   • 数学的には \(\sum_{i=1}^{N} (M - A_i)\) を計算することになります。
   • これは \((M \times N) - (\sum A_i)\) と書き換えることができ、合計値を一度に引く形でも計算可能です。

計算量

• 時間計算量: \(O(N)\)
  • 数列の最大値の探索に \(O(N)\)、合計値の計算に \(O(N)\) かかるため、全体で \(O(N)\) となります。\(N \leq 2 \times 10^5\) なので、十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の要素をリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 大きな値の扱い: \(N=2 \times 10^5\)、 \(A_i=10^9\) の場合、合計値は最大で \(2 \times 10^{14}\) 程度になります。Pythonでは自動的に多倍長整数として扱われるため問題ありませんが、他の言語（C++など）では 64bit 整数型（long long など）を使用する必要があります。

• 効率的な入力: \(N\) が大きいため、Pythonでは sys.stdin.read().split() などを使って高速に入力を読み込む工夫をすると実行時間を短縮できます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 1番目の要素が N
    n = int(input_data[0])
    # 2番目以降の要素が A_1, A_2, ..., A_N
    a = list(map(int, input_data[1:]))
    
    # 現在の水の量の最大値を取得
    max_val = max(a)
    # 現在の水の量の合計を取得
    total_sum = sum(a)
    
    # すべての花壇を最大値に合わせるために必要な費用の合計
    # 各花壇について (max_val - A_i) を足し合わせたもの
    # つまり、n * max_val - sum(a) となる
    ans = n * max_val - total_sum
    
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    main()

この解説は gemini-3-flash-preview によって生成されました。