Solution Notes: We can calculate K by taking the total number of hay bales and dividing by N. Now that we know the target height K of each pile, let X be the total number of hay bales sitting at height above K. Each one of these hay bales must be moved at some point, so we know the optimal solution has to be at least as large as X. Moreover, we can always get by with moving at most X haybales by repeatedly moving a bale from any pile taller than K to any pile shorter than K until every pile has height K. Therefore, the answer is exactly X. It is important to note with this problem that we don't need to "explicitly" compute how the hay bales are supposed to be re-distributed in order to solve the problem.

``````
#include <stdio.h>
#define MAX_N 10000

int N, K, A[MAX_N];

int main(void)
{
int i, sum=0, answer=0;

freopen ("haybales.in", "r", stdin);
freopen ("haybales.out", "w", stdout);

scanf ("%d", &N);
for (i=0; i<N; i++) {
scanf ("%d", &A[i]);
sum += A[i];
}

K = sum / N;
for (i=0; i<N; i++)
if (A[i] > K)
answer += A[i] - K;