ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 AI: 负载平衡

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：23 通过：7
返回比赛提交提交记录

题目描述

     在学校的计算机房里有n台服务器，负责处理几个计算任务。你知道每台服务器的计划任务数：有mi 个任务分配给第i台服务器。

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

     在一秒钟内，你可以重新分配一个任务。因此，在一秒钟内，你可以选择任何一对服务器，将一个任务从一个服务器转移到另一个服务器。

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

In the school computer room there are n servers which are responsible for processing several computing tasks. You know the number of scheduled tasks for each server: there are mi tasks assigned to the i-th server.
In order to balance the load for each server, you want to reassign some tasks to make the difference between the most loaded server and the least loaded server as small as possible. In other words you want to minimize expression ma-mb, where a is the most loaded server and b is the least loaded one.
In one second you can reassign a single task. Thus in one second you can choose any pair of servers and move a single task from one server to another.
Write a program to find the minimum number of seconds needed to balance the load of servers.
Input
The first line contains positive number n (1≤n≤105) − the number of the servers.
The second line contains the sequence of non-negative integers m1,m2,...,mn (0≤mi≤2·104), where mi is the number of tasks assigned to the i-th server.
Output
Print the minimum number of seconds required to balance the load.
Examples
Input 
2
1 6
Output 
2
Input 
7
10 11 10 11 10 11 11
Output 
0
Input 
5
1 2 3 4 5
Output 
3
Note
In the first example two seconds are needed. In each second, a single task from server #2 should be moved to server #1. After two seconds there should be 3 tasks on server #1 and 4 tasks on server #2.
In the second example the load is already balanced.
A possible sequence of task movements for the third example is:
  1. move a task from server #4 to server #1 (the sequence m becomes: 2 2 3 3 5);
  2. then move task from server #5 to server #1 (the sequence m becomes: 3 2 3 3 4);
  3. then move task from server #5 to server #2 (the sequence m becomes: 3 3 3 3 3).
The above sequence is one of several possible ways to balance the load of servers in three seconds.

输入格式

第一行包含正数n（1≤n≤105）--服务器的数量。

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

输出格式

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

输入样例 复制 

2
1 6

输出样例 复制 

2

数据范围与提示

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

在第二个例子中，负载已经平衡了。

对于第三个例子，可能的任务移动顺序是:

将一个任务从服务器#4移动到服务器#1(序列m变成:2 2 3 3 5);

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

然后将任务从服务器#5移动到服务器#2(顺序m变为:3 3 3 3 3 3 3)。

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

分类标签