Overview

Given that the only allowed operation on each flower bed’s water amount \(A_i\) is “add 1 liter (costs 1 yen),” find the minimum cost to make all water amounts equal.

Analysis

This operation can only “increase” water — it cannot “decrease” it.
Therefore, to make all flower beds have the same value \(X\), we must have \(X \ge \max(A_i)\) (since we cannot reduce the flower bed with the maximum value).

If we set the target value to \(X\), the required additional amount (cost) is: - \(X - A_i\) liters for flower bed \(i\) - A total of \(\sum_{i=1}^{N} (X - A_i)\) yen

This expression monotonically increases as \(X\) grows (increasing \(X\) by 1 adds \(N\) to the total across all flower beds).
Therefore, the minimum is achieved at the smallest \(X\) satisfying the condition, namely: - \(X = \max(A_i)\)

Concrete example: When \(A=[2,5,4]\), \(\max(A)=5\).
To equalize to \(X=5\): \((5-2)+(5-5)+(5-4)=3+0+1=4\) yen.
If we set \(X=6\): \((6-2)+(6-5)+(6-4)=4+1+2=7\) yen, which is larger and not minimal.

Naively simulating the operation of “adding 1 liter at a time” would not finish in a realistic time frame since the difference can be up to \(10^9\) (causing TLE).
What we need is not to count individual operations but to compute the sum of differences all at once.

Algorithm

1. Find the maximum value \(mx=\max(A)\) of the array \(A\).
2. Compute the answer as \(\sum_{i=1}^{N} (mx - A_i)\).
3. Output that total.

Complexity

• Time complexity: \(O(N)\) (computing the maximum and the sum)
• Space complexity: \(O(1)\) (additional space excluding the input array)

Implementation Notes

• The answer can be as large as approximately \(N \times (10^9-1)\), so depending on the language, you may need to use a 64-bit integer type (Python automatically handles arbitrary-precision integers, so there’s no concern).

• Since the input can be large, using sys.stdin.readline in Python provides more stable performance.

  Source Code

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

This editorial was generated by gpt-5.2-high.