No.198 Candy Box 2
nmnmnmnmnmnmnmProblem Statement
There are N boxes containing candies.
The i-th box contains Ci candies.
A-kun has been told to make the number of candies in all the boxes the same.
A-kun has B candies on hand.
A-kun can perform the following 2 operations.
・Put 1 candy from his hand into any one of the boxes.
・Take 1 candy out of any one of the boxes and add it to the candies on his hand.
A-kun wants to minimize the number of operations as much as possible.
What is the minimum number of operations A-kun must perform?
Input
$B$ $N$ $C_1$ $C_2$ $\vdots$ $C_N$
$B$ is the number of candies A-kun initially has on hand. $0 \le B\le 1000000000=10^9$.
$N$ is the number of candy boxes. $1 \le N\le 10$.
$C_i$ is the number of candies initially in the $i$-th box. $0 \le C_i\le 1000000000=10^9$.
Output
Output in one line the minimum number of operations A-kun must perform to make the number of candies in all the boxes the same.
Do not forget the newline at the end.
Sample
Sample 1
Input
1 3 0 1 2
Output
2
A-kun has 1 candy on hand from the start.
There are 3 candy boxes, containing 0, 1, and 2 candies respectively.
By putting 1 candy into the empty box and taking 1 candy from the box with 2 candies, A-kun can make every box contain 1 candy.
Sample 2
Input
1 3 0 0 1
Output
1
A-kun has 1 candy on hand from the start.
There are 3 candy boxes, containing 0, 0, and 1 candies respectively.
By taking the candy out of the box with 1 candy, A-kun can make every box contain 0 candies.
Sample 3
Input
0 4 0 4 2 2
Output
4
Take 2 candies out of the box with 4 candies and hold them on hand.
Put the 2 candies on hand into the box with 0 candies.
With 4 operations, every box contains 2 candies.
Sample 4
Input
1000000000 1 1000000000
Output
0
No operations are needed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。