概要

すべての花壇の水の量を同じにするために、最小のコストで水を追加する問題。

考察

各操作では任意の花壇に \(1\) リットルの水を \(1\) 円で追加できます。最終的にすべての花壇の水量を等しくしたいので、最も水量が多い花壇に合わせるのが最適です。なぜなら、それより多くしても無駄ですし、少ない花壇は調整できません。

たとえば、\(A = [1, 3, 2]\) の場合、最大値は \(3\) なので、それぞれの花壇に \(2, 0, 1\) リットル追加すればよく、合計コストは \(3\) になります。

素朴な方法として、全花壇の水を少しずつ増やすことは考えられますが、結局最大値に合わせる以外に意味がないため、それが最適解となります。

アルゴリズム

1. まず、すべての花壇の中から最大の水量 \( \max(A) \) を求めます。
2. 各花壇 \( i \) について、\( \max(A) - A_i \) だけ水を追加する必要があるので、これを合計します。
3. この合計が求める最小コストです。

計算量

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

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用しています。
• 最大値を一度だけ求めることで効率よく計算できます。

## ソースコード

```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]))
    
    # 最大値を基準に設定する
    max_water = max(A)
    
    # 各花壇がmax_waterに達するまでに必要な水の量を計算
    total_cost = sum(max_water - a for a in A)
    
    print(total_cost)

if __name__ == "__main__":
    main()

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