CF609C Load Balancing

在学校的计算机房里有 $n$ 台服务器，负责处理若干计算任务。你知道每台服务器被分配了多少个任务：第 $i$ 台服务器被分配了 $m_{i}$ 个任务。 为了平衡每台服务器的负载，你想要重新分配一些任务，使得负载最重的服务器与负载最轻的服务器之间的任务数差尽可能小。换句话说，你想要最小化表达式 $m_{a} - m_{b}$，其中 $a$ 表示负载最重的服务器，$b$ 表示负载最轻的服务器。 你每秒可以重新分配一个任务。也就是说，在每一秒钟，你可以选择任意一对服务器，并将其中一台服务器的一个任务转移到另一台服务器上。 请编写一个程序，计算最少需要多少秒才能平衡服务器的负载。

第一行包含一个正整数 $n$（$1 \leq n \leq 10^{5}$），表示服务器的数量。 第二行包含 $n$ 个非负整数 $m_{1}, m_{2},...,m_{n}$ （$0 \leq m_{i} \leq 2 \times 10^{4}$），其中 $m_{i}$ 表示第 $i$ 台服务器被分配的任务数量。

输出使服务器负载尽可能平衡所需的最少秒数。

在第一个样例中，需要两秒钟。在每一秒钟，将服务器 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）。 上述移动方案就是在三秒内平衡服务器负载的多种方法之一。 由 ChatGPT 5 翻译