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 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+=a, 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