CodeForces 609C-C. Load Balancing

左手的ㄟ右手 2022-08-19 12:11 103阅读 0赞

C. Load Balancing

time limit per test 2 seconds

memory limit per test 256 megabytes

input standard input

output standard output

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*m**i* 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*m**a* - *m**b*, 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 *m*1, *m*2, ..., *m**n* (0 ≤ *m**i* ≤ 2·104), where *m**i* is the number of tasks assigned to the*i*\-th server.

Output

Print the minimum number of seconds required to balance the load.

Sample test(s)

Input

2
    1 6

Output

Input

7
    10 11 10 11 10 11 11

Output

Input

5
    1 2 3 4 5

Output

解题思路：

这里给出一串数字，要将他调整成为平衡的数组，就是左右差不超过一，每次可以任选两个元素使得其中一个减1，另一个加1，付出代价为1。问你最小的代价使得序列最平衡。先计算出平衡时的上限和下限，显然小于下限的我们要提到Min，大于上限的我们要降到Max，而每次升和降是可以用代价1实现的。这样统计两边的代价，取最大值就好了。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int map[10000000];
    int Max(int x,int y)
    {
    	return max(x,y);
    }
    int main()
    {
    	int n;
    	while(scanf("%d",&n)!=EOF)
    	{
    		int sum=0;
    		int i,j;
    		for(i=0;i<n;i++)
    		{
    			scanf("%d",&map[i]);
    			sum+=map[i];
    		}
    		int max,min;
    		max=min=sum/n;
    		if(sum%n)
    		max++;
    		int ans1=0,ans2=0;
    		for(i=0;i<n;i++)
    		{
    			if(map[i]<min)
    			{
    				ans1+=min-map[i];
    			}
    			else if(map[i]>max)
    			{
    				ans2+=map[i]-max;
    			}
    		}
    		printf("%d\n",Max(ans1,ans2));
    	}
    	return 0;
    }