P1031 [NOIP2002 提高组] 均分纸牌

简单贪心题。

如果每个数相等时的数为sum,考虑一个数不等于sum,最好的情况通过一次转移使它变为sum。

所以按顺序处理，当前数少从后面拿，当前数多向后面扔，中间记录次数即可。

考虑正确性，有人会觉得，如果后面的数不够拿成为了负数，需要从更后面拿，就不止一次转移了。

其实，如果遇到上述情况，可以先做后面的数从更后面拿数的操作，再做当前数拿数操作，这样操作总数不变。

由此可证，只要不等于sum,拿一次就好了。

#include <bits/stdc++.h>
using namespace std;
int n,a[110],sum,ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
    sum/=n;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>sum) ans++,a[i+1]+=a[i]-sum;
        else if(a[i]<sum) ans++,a[i+1]-=(sum-a[i]);
    }
    printf("%d",ans);
    return 0;
}