Problem Description

There are n piles of cards, numbered from 1 to n. Each pile contains a certain number of cards, and the total number of cards is guaranteed to be a multiple of n. You can take any number of cards from a pile and move them according to the following rules:

• Cards taken from pile 1 can only be moved to pile 2.
• Cards taken from pile n can only be moved to pile n-1.
• Cards taken from any other pile can be moved to either the left or right adjacent pile.

The goal is to find a method that uses the minimum number of moves to make all piles have the same number of cards.

Example

For n=4 with piles containing 9, 8, 17, and 6 cards respectively:

• Move 4 cards from pile 3 to pile 4 → (9, 8, 13, 10)
• Move 3 cards from pile 3 to pile 2 → (9, 11, 10, 10)
• Move 1 card from pile 2 to pile 1 → (10, 10, 10, 10) This requires 3 moves.

Input

• n (1 ≤ n ≤ 100)
• a1 a2 … an (1 ≤ ai ≤ 10000)

Output

The minimum number of moves required to equalize all piles.

Solution Approach

A greedy algorithm can efficiently solve this problem. The key insight is to process the piles sequentially from left to right, adjusting each pile to the target average by transferring cards to or from the next pile. This ensures minimal moves since each adjustment is made locally and only when necessary.

Algorithm Steps

1. Calculate the total number of cards and the target number per pile (total / n).
2. Iterate through each pile from the first to the second-to-last:
   • If the current pile has exactly the target number, skip it.
   • If it has more than the target, transfer the excess to the next pile and increment the move count.
   • If it has fewer than the target, take the deficit from the next pile and increment the move count.
3. The move count after processing all piles is the answer.

Code Implementation

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

int main() {
    int pileCount;
    cin >> pileCount;
    vector<int> cards(pileCount);
    int totalCards = 0;
    
    for (int i = 0; i < pileCount; i++) {
        cin >> cards[i];
        totalCards += cards[i];
    }
    
    int targetPerPile = totalCards / pileCount;
    int moveCount = 0;
    
    for (int i = 0; i < pileCount - 1; i++) {
        if (cards[i] == targetPerPile) {
            continue;
        } else if (cards[i] > targetPerPile) {
            int excess = cards[i] - targetPerPile;
            cards[i + 1] += excess;
            moveCount++;
        } else {
            int deficit = targetPerPile - cards[i];
            cards[i + 1] -= deficit;
            moveCount++;
        }
    }
    
    cout << moveCount << endl;
    return 0;
}

Explanation

• The algorithm processes each pile in order, ensuring that by the time we reach the last pile, all piles will have the target number of cards.
• The move count increments only when a transfer is necessary, which aligns with the problem's requirement for minimal moves.
• This approach works because the total number of cards is fixed, and transfers are only made to adjacent piles, satisfying the movement constraints.

Complexity Analysis

• Time Complexity: O(n), where n is the number of piles, as we make a single pass through the array.
• Space Complexity: O(n) for storing the pile counts, or O(1) if modified in-place with out additional data structures.

This greedy solution is optimal for this problem, as demonstrated by its acceptance in programming contests like NOIP.