Overview

This is a problem where we want to minimize the total amount shaved off when making all \(N\) apples equal in weight through a shaving operation. Each apple has a uniform coating agent weight \(R\) added to it.

Analysis

The key to solving this problem is to think about “what target weight should we set to minimize the total amount shaved?”

1. Determining the target weight \(X\)

The weight of each apple after coating is \(A_i + R\) grams. Since we can “shave” apples but cannot “add” to them, to make all apples the same weight \(X\), \(X\) must be less than or equal to the current weight of every apple. In other words, \(X \leq \min(A_1+R, A_2+R, \dots, A_N+R)\).

To minimize the amount shaved, we should make the final weight \(X\) as large as possible, so setting \(X\) to the minimum weight after coating is optimal. $\(X = \min(A_i + R)\)$

2. The effect of coating agent \(R\)

The amount shaved from each apple can be calculated as \((\text{current weight}) - (\text{target weight } X)\). For apple \(i\), this is computed as follows: $\((A_i + R) - (\min(A) + R) = A_i - \min(A)\)$

Here we notice an important fact. Since the same amount \(R\) is added to all apples, the differences in weight between apples do not change before and after coating. Therefore, the value of \(R\) does not affect the result when considering minimization.

3. Concrete example

For example, if \(A = [10, 12, 15], R = 5\): - After coating: \([15, 17, 20]\) - The minimum is \(15\), so we set the target weight to \(15\). - Amount shaved: \((15-15) + (17-15) + (20-15) = 0 + 2 + 5 = 7\)

This matches the result calculated using the minimum value \(10\) of the original weights \(A\): \((10-10) + (12-10) + (15-10) = 7\).

Algorithm

1. Find the minimum value \(min\_A\) among the input \(A_1, A_2, \dots, A_N\).
2. For each \(A_i\), calculate \(A_i - min\_A\) and find the total sum.
   • Expressed as a formula: \(\sum_{i=1}^{N} (A_i - \min(A))\)
   • With a computational shortcut, this can also be computed as: \((\sum A_i) - N \times \min(A)\)

Complexity

• Time complexity: \(O(N)\)
  • Finding the minimum of the list takes \(O(N)\), and computing the sum takes \(O(N)\). Since \(N \leq 2 \times 10^5\), this is sufficiently fast.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the \(N\) input weights in a list.

Implementation Notes

• The value of \(R\) can be very large, but as shown in the analysis, it is not needed for the calculation, so it can safely be ignored in the implementation.

• The total value may exceed \(2^{31}-1\), so depending on the programming language, be careful to use a 64-bit integer type (Python handles this by default).

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: りんごの個数, R: コーティング剤の重さ
    N = int(input_data[0])
    R = int(input_data[1])
    
    # A: 各りんごの元の重さ
    A = list(map(int, input_data[2:]))
    
    # コーティング後の各りんごの重さは W_i = A_i + R
    # すべてのりんごの重さを等しくするために削る量を最小にするには、
    # 目標とする重さ X を「コーティング後の重さの最小値」に設定すればよい。
    # X = min(A_1 + R, A_2 + R, ..., A_N + R) = min(A) + R
    
    # 各りんごから削る量は (A_i + R) - X
    # (A_i + R) - (min(A) + R) = A_i - min(A)
    
    # したがって、削る量の合計は sum(A_i - min(A)) となる
    # これは R の値に依存しない
    
    min_a = min(A)
    total_shaved = sum(A) - N * min_a
    
    print(total_shaved)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.