P1031 均分纸牌

题目

分析

先求出平均数，再把每堆牌的数都减去平均数，再移动正数加到负数中，使每堆牌都为0即可。然后，考虑左右两端从哪里开始。就是左边第一个不为0的到右边最后一个不为0的。

源代码

#include<cstdio>
#include<iostream>

using namespace std;
int array[101];
int main()
{
	int n,i,j,sum=0,he=0,average,step=0;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>array[i];
		he+=array[i];
	}
	average=he/n;
	for(i=1;i<=n;i++)array[i]-=average;
	int begin,end;
	for(i=1;i<=n;i++)
	{
		if(array[i]!=0)
		{
			begin=i;
			break;
		}
	}
	for(i=n;i>0;i--)
	{
		if(array[i]!=0)
		{
			end=i;
			break;
		}
	}
	while(begin<end)
	{
		array[begin+1]+=array[begin];
		array[begin]=0;
		step++;
		begin++;
		while(array[begin]==0&&begin<end)begin++;
	}
	cout<<step<<endl;
	return 0;
 }

结果

这就是一道典型的贪心算法题。