example_response_hay_bales.txt

Okay, I need to solve this problem where Farmer John's cows messed up the hay bale piles, and I have to find the minimum number of hay bales he needs to move to get them all back to equal heights. Hmm.

So, let's think about it. The initial state had all piles of the same height. Then cows moved some, so now each pile can be different. But Farmer John needs to bring them all back to the same height. Wait, but what was the original height? Oh, right, the problem statement says that the initial heights were all the same. So, I think I need to find what the target height is, and then compute how many moves are needed to reach that.

Wait, but wait a minute. Wait, in the problem statement, the original arrangement has all piles of the same height. So, the problem is, after some changes, the heights are now given. We have to find the target height (which is the same for all piles) that requires the minimum number of hay bales to be moved.

Alternatively, no—wait, perhaps the initial height was not known. Because in the problem statement, it says that the initial heights were all equal, but after the cows messed up, they have varying heights. So, perhaps the target is to bring them back to the same height, but what was that original height?

Wait, perhaps the original height can be calculated. Because the sum of all the hay bales is the same in the initial and final state. Because moving hay bales between piles doesn't change the total. So, the total sum is fixed. Therefore, the target height must be the total sum divided by the number of piles, right?

Yes, that makes sense. Because initially, all piles had the same height, say H. Then sum(H * N) is the total. After cows move, the sum remains the same. So, to get back to all piles equal, each pile must be of height total / N.

But wait, that assumes that total is divisible by N. But in the problem statement, it's given that N can be up to 10,000, and the heights are up to 10,000. So, when I compute the sum, I have to make sure that it's divisible by N. Otherwise, it's impossible. But according to the problem statement, the cows just move hay bales, so the sum remains the same. Therefore, the target height must be sum / N.

So, the steps are:

1. Calculate the total sum of all the piles.
2. The target height is sum / N.
3. For each pile, calculate the difference between the current height and the target. If it's above, they need to give away (current - target) bales. If it's below, they need to receive (target - current) bales.
4. But since we can only move hay bales from those above to those below, the total number of moves required is the sum of the excess from each pile, which equals the sum of the deficits (since the total sum is the same before and after).

So, to find the minimum number of moves, we need to sum all the positive differences between each pile's current height and the target. That's the total number of hay bales that need to be moved.

Wait, but that's the number of moves? Because each hay bale that needs to be moved is a transfer from one pile to another. So, the total number of moves is the sum of the excess in each pile.

So, the algorithm is straightforward:

- Compute sum of all piles.
- Compute target = sum / N.
- For each pile, compute (current height - target). If it's positive, add it to the total moves. If it's negative, ignore (since those are the deficits that others will cover).
- The total moves is the sum of all the positive differences.

Let me test this with the sample input.

Sample input:

4
2
10
7
1

Sum is 2 +10+7+1=20. Target is 20/4=5.

Compute the differences:

2: 2-5= -3 → no contribution
10: 10-5=5 → add 5
7: 7-5=2 → add 2
1: 1-5=-4 → no contribution
Total moves: 5+2=7 → which matches the sample output.

Yes, that works.

Another test case: suppose N=2, with piles 3 and 5. Sum is 8, target is 4. The excess is 1 (5-4=1) and deficit is 1 (3-4= -1). So total moves is 1.

Another case: N=3, with piles 4,4,4. Sum is 12, target is 4. So all are at target. Total moves is 0.

Another case: N=1. Then only one pile, target is same as current. So moves are 0.

So, the algorithm seems solid.

So, now, the plan is to read N, read all the heights, sum them, compute target, and then sum the positive differences.

Now, coding this in C++. The steps:

1. Read N from input.
2. Read N integers, store in a vector or array.
3. Compute the sum of these integers.
4. Compute target = sum / N.
5. For each element in the array, compute (current - target). If it's positive, add to total.
6. Output the total.

Potential edge cases:

- N=1: handle correctly.
- All piles already at target: output 0.
- Piles with varying heights but sum exactly divisible by N.

Now, implement this in C++. So, let's think about the code.

Read N: easy, use cin >> N.

Read N integers: store in a vector or array. Let's use a vector for simplicity.

Compute sum: loop through the vector, add each element.

Compute target: sum / N.

Loop through each element in the vector again, compute (current - target). If it's positive, add to total.

But wait, wait a moment: if sum is not exactly divisible by N, then target is a fractional value, but in the problem statement, the initial heights were all equal, so target must be integer. So, the sum must be divisible by N. So, in code, we can safely cast sum to int and divide by N.

But in the problem statement, the input is such that it's always possible. So, the code doesn't need to handle cases where sum is not divisible by N.

So, in C++, code outline:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> piles;
    int sum = 0;
    for(int i=0; i<N; i++) {
        int h;
        cin >> h;
        piles.push_back(h);
        sum += h;
    }
    int target = sum / N;
    int moves = 0;
    for(int h : piles) {
        if (h > target) {
            moves += (h - target);
        }
    }
    cout << moves << endl;
}

Yes, that should work.

Testing this with the sample input:

N=4, piles are 2,10,7,1.

Sum is 20, target is 5.

Each h > target: 10 (5), 7 (2). Sum is 7.

Which is correct.

Another test case: N=3, piles 6,6,6. Sum is 18, target 6. So moves 0.

Another test: N=2, piles 0 and 4. Wait, but the input constraints say each h is >=1. Oh, in the input, the h can be 1, but according to the problem statement, perhaps the initial heights can be anything, but the problem says that the new heights are given as per the input. Wait, the problem statement says each pile's new height is in 1...10000. So, that's correct.

Wait, no, the initial arrangement was that all piles were same height, but the input gives the new heights after the cows messed it up. So, the new heights can be any numbers, as per the problem statement.

So, the code will handle it.

So, the code should be correct.
</think>

To solve this problem, we need to determine the minimum number of hay bales that need to be moved to restore all piles to their original equal height. The key insight is that the total number of hay bales remains constant, so the target height for each pile is the total number of hay bales divided by the number of piles.

### Approach
1. **Read Input**: Read the number of piles and their respective heights.
2. **Calculate Total Hay Bales**: Compute the sum of all the hay bales in the piles.
3. **Determine Target Height**: The target height for each pile is the total number of hay bales divided by the number of piles.
4. **Compute Moves**: For each pile, calculate the difference between its current height and the target height. Sum these differences for all piles where the current height exceeds the target height. This sum gives the minimum number of hay bales that need to be moved.

### Solution Code
```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> piles;
    int sum = 0;
    for(int i = 0; i < N; i++) {
        int h;
        cin >> h;
        piles.push_back(h);
        sum += h;
    }
    int target = sum / N;
    int moves = 0;
    for(int h : piles) {
        if (h > target) {
            moves += (h - target);
        }
    }
    cout << moves << endl;
}
```

### Explanation
- **Reading Input**: The code reads the number of piles and their respective heights.
- **Sum Calculation**: It calculates the total number of hay bales across all piles.
- **Target Height**: The target height is computed as the total hay bales divided by the number of piles.
- **Move Calculation**: For each pile, if its height is greater than the target height, the excess hay bales are counted. The sum of these excess values gives the minimum number of hay bales that need to be moved.

This approach efficiently computes the required result with a time complexity of O(N), where N is the number of piles, making it suitable for the given problem constraints.