Overview

A problem where we need to add water at minimum cost to make the amount of water in all flower beds equal.

Analysis

In each operation, we can add \(1\) liter of water to any flower bed for \(1\) yen. Since we want all flower beds to have equal water amounts in the end, the optimal strategy is to match the flower bed with the most water. This is because adding more than that would be wasteful, and we cannot reduce the water in flower beds that already have too much.

For example, if \(A = [1, 3, 2]\), the maximum value is \(3\), so we need to add \(2, 0, 1\) liters to each flower bed respectively, giving a total cost of \(3\).

A naive approach might consider gradually increasing the water in all flower beds, but since there is no benefit other than matching the maximum value, this is the optimal solution.

Algorithm

1. First, find the maximum water amount \( \max(A) \) among all flower beds.
2. For each flower bed \( i \), we need to add \( \max(A) - A_i \) amount of water, so we sum these up.
3. This sum is the minimum cost we are looking for.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input data)

Implementation Notes

• We use sys.stdin.read for fast input reading.
• By computing the maximum value only once, we can calculate the result efficiently.

## Source Code

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

This editorial was generated by qwen3-coder-480b.