Overview

This problem asks us to minimize the total amount shaved off to make all \(N\) apples the same weight after applying a coating agent.

Analysis

Key Observations

1. Apples can only be shaved (weight can only be reduced)

   • This means the target weight \(X\) cannot be heavier than the lightest apple
   • If \(X\) is heavier than the lightest apple, it’s impossible to bring that apple’s weight to \(X\)

2. Expressing the total amount shaved as a formula

   • Let the weight of each apple after coating be \(W_i = A_i + R\)
   • When making all apples weigh \(X\), the total amount shaved is: $\(\sum_{i=1}^{N} (W_i - X) = \sum_{i=1}^{N} W_i - N \times X\)$

3. How to minimize the amount shaved?

   • Looking at the formula above, since \(\sum W_i\) is a fixed value, we can see that we should maximize \(N \times X\)
   • In other words, maximizing \(X\) minimizes the amount shaved

4. What is the maximum value of \(X\)?

   • \(X\) must be less than or equal to the weight of the lightest apple \(\min(W_i)\)
   • Therefore, \(X = \min(W_i)\) is optimal

Verification with a Concrete Example

For example, if the weights after coating are \([5, 8, 6]\): - The minimum is \(5\), so the target weight \(X = 5\) - Amount shaved = \((5-5) + (8-5) + (6-5) = 0 + 3 + 1 = 4\)

This matches \(\sum W_i - N \times X = (5+8+6) - 3 \times 5 = 19 - 15 = 4\).

Algorithm

1. Calculate the weight of each apple after coating \(W_i = A_i + R\)
2. Find the minimum weight after coating \(\min(W_i)\)
3. Find the total sum of weights after coating \(\sum W_i\)
4. Output the total amount shaved \(= \sum W_i - N \times \min(W_i)\)

Complexity

• Time complexity: \(O(N)\)
  • \(O(N)\) to compute the sum of the array
  • \(O(N)\) to find the minimum value
• Space complexity: \(O(N)\)
  • \(O(N)\) for the array storing weights after coating
  • (This can be optimized to \(O(1)\), but we use an array for readability)

Implementation Notes

• Since \(R\) and \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total sum can be approximately \(2 \times 10^{14}\). In Python, there’s no need to worry about integer overflow, but in other languages (such as C++), you need to use 64-bit integer types.
• Instead of storing weights after coating in a separate array, you can directly calculate min(A) + R and sum(A) + N * R.

Source Code

def solve():
    N, R = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Weights after coating
    weights = [a + R for a in A]
    
    # Minimize the total amount shaved to make all apples equal in weight
    # The final weight X must be at most the minimum weight (since we cannot increase weight)
    # Total amount shaved = Σ(weights[i] - X) = Σweights[i] - N * X
    # To minimize this, we should maximize X
    # The maximum value of X is min(weights)
    
    min_weight = min(weights)
    total_sum = sum(weights)
    
    # Total amount shaved = total weight - N * (target weight)
    result = total_sum - N * min_weight
    
    print(result)

solve()

This editorial was generated by claude4.5opus.