Approximate Equalization 2

题目描述

给定一个整数序列 $A=(A_1,A_2,\dots,A_N)$。 你可以任意次（可能为零次）执行以下操作。

选择整数 $i$ 和 $j$，使得 $1\leq i,j \leq N$。将 $A_i$ 减一并将 $A_j$ 加一。

求使得序列 $A$ 的最小值与最大值之差至多为一所需的最小操作次数。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

以整数形式输出答案。

4
4 7 3 7

3

1
313

0

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

2499999974

提示

$1\leq N \leq 2\times 10^5$ $1\leq A_i \leq 10^9$ 所有输入值均为整数。通过如下三次操作，序列 $A$ 的最大值与最小值之差可变为至多一。

选择 $i=2$ 和 $j=3$ 使得 $A=(4,6,4,7)$。 选择 $i=4$ 和 $j=1$ 使得 $A=(5,6,4,6)$。 选择 $i=4$ 和 $j=3$ 使得 $A=(5,6,5,5)$。

不能通过少于三次操作使 $A$ 的最大值与最小值之差至多为一，因此答案为 $3$。

标签: AtCoder|abc313C

来源

AtCoder|abc313C