# P1031 divide cards equally (greedy)

2021-08-10 08:04:05

## P1031 Divide the cards equally （ greedy ）

Subject portal

The question ：N Stack cards to find the minimum number of moves so that the number of cards in each stack is the same （ The optimal solution is guaranteed and can only move adjacent ）

Ideas ： According to greedy thought ： Obviously, two adjacent stacks of cards can move at most once , We calculate the difference between each pile of cards and the average , obtain ( Number of difference or more ） So let's start with the first pile of cards , If the difference a[1] Not for 0, It means that these two adjacent piles need to be moved once , The difference of the first pile can only be given by the second pile , So update the difference of the second pile a[2]+=a[1], Then the first pile is finished, regardless of , At this time, the second pile can be regarded as the current first pile , Keep pushing , You can calculate the result .

``````#include<bits/stdc++.h>
using namespace std;
int main(){
int n,sum=0;
cin>>n;
int a[n+1],ans=0;
for(int i=1;i<=n;i++)
cin>>a[i],sum+=a[i];;
sum/=n;
for(int i=1;i<=n;i++)
a[i]-=sum;
for(int i=1;i<=n;i++)
if(a[i]) a[i+1]+=a[i],ans++;
cout<<ans<<endl;
return 0;
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
```

https://chowdera.com/2021/08/20210810080205535t.html