← 返回题目列表

Codeforces · 609/C

C. 负载平衡

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

学校机房有n台服务器,负责处理多项计算任务。您知道每个服务器的计划任务数量:有 mi 个任务分配给第 i 个服务器。

为了平衡每台服务器的负载,您希望重新分配一些任务,以使负载最多的服务器和负载最少的服务器之间的差异尽可能小。换句话说,您希望最小化表达式 ma - mb,其中 a 是负载最多的服务器,b 是负载最少的服务器。

您可以在一秒钟内重新分配单个任务。因此,您可以在一秒钟内选择任意一对服务器并将单个任务从一台服务器移动到另一台服务器。

编写一个程序来查找平衡服务器负载所需的最小秒数。

输入

第一行包含正数 n (1 ≤ n ≤ 105) — 服务器数量。

第二行包含非负整数序列 m1, m2, ..., mn (0 ≤ mi ≤ 2·104),其中 mi 是分配给第 i 个服务器的任务数。

输出

打印平衡负载所需的最小秒数。

示例

输入 #1

2
1 6

输出 #1

2

输入 #2

7
10 11 10 11 10 11 11

输出 #2

0

输入 #3

5
1 2 3 4 5

输出 #3

3

注意

在第一个示例中需要两秒钟。每一秒,服务器#2 中的一个任务应移动到服务器#1。两秒后,服务器 #1 上应有 3 个任务,服务器 #2 上应有 4 个任务。

在第二个示例中,负载已经平衡。

第三个示例的可能的任务移动顺序是:

1. 将任务从服务器 #4 移动到服务器 #1(序列 m 变为:2 2 3 3 5);
2.然后将任务从服务器#5移动到服务器#1(序列m变为:3 2 3 3 4);
3. 然后将任务从服务器 #5 移动到服务器 #2(序列 m 变为:3 3 3 3 3)。

上述序列是在三秒内平衡服务器负载的几种可能方法之一。