Overview

This problem asks for the minimum cost to make the water amount in all flower beds equal by adding water to each bed. Since we can only add water, the optimal strategy is to match everything to the maximum value.

Analysis

Key Insight

In this problem, we can only perform the operation of “adding water.” Since we cannot reduce water, the target value to equalize all flower beds must be at least the current maximum value.

Why Matching to the Maximum is Optimal

If we set the target value to \(T\), the required cost is the sum of \((T - A_i)\) for each flower bed, which equals \(N \times T - \sum A_i\).

• As \(T\) increases, the cost increases
• \(T\) must be at least \(\max(A_i)\) (since we cannot reduce water)

Therefore, the cost is minimized when \(T = \max(A_i)\).

Concrete Example

Consider the case where \(N = 3\) and \(A = [2, 5, 3]\).

• The maximum value is \(5\)
• Flower bed 1: Add \(5 - 2 = 3\) liters (3 yen)
• Flower bed 2: Add \(5 - 5 = 0\) liters (0 yen)
• Flower bed 3: Add \(5 - 3 = 2\) liters (2 yen)
• Total: \(3 + 0 + 2 = 5\) yen

This can be calculated as \(5 \times 3 - (2 + 5 + 3) = 15 - 10 = 5\).

Algorithm

1. Find the maximum value \(\max(A)\) of array \(A\)
2. Find the sum \(\sum A_i\) of array \(A\)
3. The answer is \(\max(A) \times N - \sum A_i\)

Meaning of this formula: - \(\max(A) \times N\): Total amount of water when all flower beds are equalized to the maximum - \(\sum A_i\): Current total amount of water - The difference is the amount of water to add (= cost)

Complexity

• Time complexity: \(O(N)\)
  • Computing the maximum: \(O(N)\)
  • Computing the sum: \(O(N)\)
• Space complexity: \(O(N)\)
  • For storing array \(A\)

Implementation Notes

• Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the answer can be approximately \(2 \times 10^{14}\) at maximum. In Python, there’s no need to worry about integer overflow, but in C++ and similar languages, you need to use the long long type.

• Using Python’s max() and sum() functions allows for a concise implementation.

  Source Code

N = int(input())
A = list(map(int, input().split()))

max_water = max(A)
total_cost = max_water * N - sum(A)

print(total_cost)

---

This editorial was generated by claude4.5opus.