AT_abc313_c [ABC313C] Approximate Equalization 2

题目描述

有一个整数序列 $A=(A_1,A_2,\dots,A_N)$。你可以进行任意次数（也可以为 $0$ 次）如下操作：

• 选择满足 $1\leq i,j \leq N$ 的整数 $i,j$。将 $A_i$ 减去 $1$，将 $A_j$ 加上 $1$。

请你求出，为了使 $A$ 的最小值与最大值之差不超过 $1$，所需的最少操作次数。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出一个整数，表示答案。

输入输出样例 #1

输入 #1

4
4 7 3 7

输出 #1

3

输入输出样例 #2

输入 #2

1
313

输出 #2

0

输入输出样例 #3

输入 #3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

输出 #3

2499999974

说明/提示

限制条件

• $1\leq N \leq 2\times 10^5$
• $1\leq A_i \leq 10^9$
• 输入均为整数

样例解释 1

通过如下 $3$ 次操作，可以使 $A$ 的最小值与最大值之差不超过 $1$：

• 以 $i=2, j=3$ 进行操作。$A=(4,6,4,7)$ 变为 $A=(4,6,4,7)$。
• 以 $i=4, j=1$ 进行操作。$A=(4,6,4,7)$ 变为 $A=(5,6,4,6)$。
• 以 $i=4, j=3$ 进行操作。$A=(5,6,4,6)$ 变为 $A=(5,6,5,5)$。

在少于 $3$ 次操作的情况下，无法使 $A$ 的最小值与最大值之差不超过 $1$。因此答案为 $3$。

由 ChatGPT 4.1 翻译