Description

The Problem

There are N piles of cards, and these piles are numbered as 1,2,...,N respectively. Each pile has some cards, while the total of all cards must be a multiple of N. The player can take some cards from one pile and then put them on another pile as one step.

The follow is the rules: the cards on the pile numbered 1 can only be moved to the pile 2; the cards on the pile N can only be moved to the pile N-1; the cards on other piles, numbered from 2 to N-1, can be moved to either their left pile or right one.

Now the player should move these cards to make the card numbers of each pile equal by minimum steps.

For example: there are 4 piles, and the card numbers of each pile are 9 8 17 6 respectively. So it needs 3 steps to achieve the goal at least.

The Input

The input file consists of one or more test cases. The first line of input is the number of cases. Each case contains 2 lines: the first line of each case contains the only number N indicating the number of piles, and the second line contains a group of integers separated by space, indicating the card numbers of each pile respectively.

The Output

The minimum steps to make all piles' card numbers equal.

 

Sample input

149 8 17 6

Sample output

3 水题一道 附上题目链接

1 #include
     
       2 #include
      
        3 using namespace std; 4 int main (){ 5     int cases; 6     cin>>cases; 7     int add , count; 8     int average , N; 9     while ( cases-- )10     {11         average=count=add=0;12         cin>>N;13         vector
       
        pile (N);14         for ( int i=0; i
        
         >pile[i];17             average += pile[i];18         }19         average/=N;20         for ( int j=0; j