STATUES - Editorial

editorial
, ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

TRIVIAL

PREREQUISITES

None

PROBLEM

There are N rooms with A1, A2, …, AN statues in them respectively. You wish to make the number of statues in all the rooms equal. You have only one kind of move available to you.

Move a statue from one room to another.

You are also assured that the number of statues are a multiple of N. What is the minimum number of moves required to make the number of statues in all the rooms equal?

EXPLANATION

First, we find the number of statues that every room must have eventually. This is simply the average number of statues per room.

sum = 0
for i = 1 to N
	sum = sum + Ai
average = sum / N

Let Di store the difference between the statues in the ith room and the average number of statues calculated above.

for i = 1 to N
	Di = Ai - average

We know that the sum of the values of Di’s is equal to 0.

That means, the sum of positive values in D is equal to the absolute value of the sum of negative values in D. In fact, in the optimal strategy, we will always try to move a statue from a room with surplus - i.e. positive Di - to a room with deficit - i.e. negative Di.

Hence, the answer is simply the sum of the positive entries in Di.

answer = 0
for i = 1 to N
	if Di > 0
		answer = answer + Di

CODE COMMENTARY

There are no real pitfalls you might fall in to.

The input parsing required you to process input till you encountered a 0 for the value of N in the input. This might be new to you, but can be easily handled in a main run loop. Check the setter’s or tester’s solution for reference.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.