codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

609C.md (2206B)


      1 Source: https://codeforces.com/problemset/problem/609/C
      2 
      3 C. Load Balancing
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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.
     24 
     25 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.
     26 
     27 Write a program to find the minimum number of seconds needed to balance the load of servers.
     28 
     29 Input
     30 
     31 The first line contains positive number *n* (1 ≤ *n* ≤ 105) — the number of the servers.
     32 
     33 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.
     34 
     35 Output
     36 
     37 Print the minimum number of seconds required to balance the load.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 2  
     45 1 6
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 2
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 7  
     58 10 11 10 11 10 11 11
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 5  
     71 1 2 3 4 5
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 3
     78 ```
     79 
     80 Note
     81 
     82 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.
     83 
     84 In the second example the load is already balanced.
     85 
     86 A possible sequence of task movements for the third example is:
     87 
     88 1. move a task from server #4 to server #1 (the sequence *m* becomes: 2 2 3 3 5);
     89 2. then move task from server #5 to server #1 (the sequence *m* becomes: 3 2 3 3 4);
     90 3. then move task from server #5 to server #2 (the sequence *m* becomes: 3 3 3 3 3).
     91 
     92 The above sequence is one of several possible ways to balance the load of servers in three seconds.