/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は、果樹園で N 個のりんごを収穫しました。りんご i (1 \leq i \leq N) の重さは A_i グラムです。
収穫後、高橋君はすべてのりんごにコーティング剤を塗りました。コーティング剤を塗ることで各りんごの重さはちょうど R グラムずつ増えるため、コーティング後のりんご i の重さは A_i + R グラムになりました。
高橋君は、これらのりんごを贈答用の箱に詰めるため、すべてのりんごの重さを同じにしたいと考えています。そこで、各りんごを削って重さを減らすことにしました。各りんごからは 0 以上の任意の整数グラムだけ削ることができます。ただし、重さを増やすことはできず、削った後の重さが 0 グラム未満になることもできません。
高橋君の目標は、すべてのりんごの重さを同じ値 X グラム（ X は 0 以上 \min(A_1+R, A_2+R, \ldots, A_N+R) 以下の整数）にすることです。このとき、すべてのりんごから削る量の合計、すなわち
\sum_{i=1}^{N} \bigl((A_i + R) - X\bigr)
を最小化したいと考えています。
この合計の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq R \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N R A_1 A_2 \ldots A_N
- 1 行目には、りんごの個数を表す整数 N と、コーティング剤によって各りんごが増加する重さを表す整数 R が、スペース区切りで与えられる。
- 2 行目には、コーティング前の各りんごの重さを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
すべてのりんごの重さを等しくするために削る量の合計の最小値を 1 行で出力してください。
入力例 1
3 5 10 12 15
出力例 1
7
入力例 2
5 100 50 30 80 30 60
出力例 2
100
入力例 3
8 1000000000 500 1200 800 950 600 1100 750 900
出力例 3
2800
Score : 233 pts
Problem Statement
Takahashi harvested N apples from an orchard. The weight of apple i (1 \leq i \leq N) is A_i grams.
After harvesting, Takahashi applied a coating agent to all the apples. Applying the coating agent increases each apple's weight by exactly R grams, so the weight of apple i after coating becomes A_i + R grams.
Takahashi wants to pack these apples into a gift box, so he wants all the apples to have the same weight. To achieve this, he decided to shave each apple to reduce its weight. Each apple can be shaved by any non-negative integer number of grams. However, the weight cannot be increased, and the weight after shaving cannot become less than 0 grams.
Takahashi's goal is to make all the apples have the same weight X grams (X is an integer satisfying 0 \leq X \leq \min(A_1+R, A_2+R, \ldots, A_N+R)). He wants to minimize the total amount shaved from all the apples, namely
\sum_{i=1}^{N} \bigl((A_i + R) - X\bigr)
Find the minimum value of this total.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq R \leq 10^9
- 1 \leq A_i \leq 10^9
- All input values are integers
Input
N R A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of apples and an integer R representing the weight increase from the coating agent for each apple, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the weight of each apple before coating, separated by spaces.
Output
Print the minimum total amount that must be shaved to make all the apples equal in weight, on a single line.
Sample Input 1
3 5 10 12 15
Sample Output 1
7
Sample Input 2
5 100 50 30 80 30 60
Sample Output 2
100
Sample Input 3
8 1000000000 500 1200 800 950 600 1100 750 900
Sample Output 3
2800