← 返回题目列表

AtCoder · abc313_c

F. 近似均衡 2

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

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

  • 选择整数 i 和 j 与 1\leq i,j \leq N。 减少 A_i 加一并增加 A_j 减一。

找出使 的最小值和最大值之间存在差异所需的最少运算次数 A 最多一个。

约束

  • 1\leq N \leq 2\times 10^5
  • 1\leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

将答案打印为整数。


示例输入 1

4
4 7 3 7

示例输出 1

3

通过以下三个运算,求出最小值和最大值之间的差值 A 最多变为 1。

  • 选择 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 至多 1 乘以少于 3 次运算,所以答案是 3.


示例输入 2

1
313

示例输出 2

0

示例输入 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

示例输出 3

2499999974