洛谷 P1031 [NOIP2002 提高组] 均分纸牌 题解

题目简述

有 $N$ 堆纸牌，编号分别为 $1,2,\ldots,N$。每堆上有若干张，但纸牌总数必为 $N$ 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 $1$ 堆上取的纸牌，只能移到编号为 $2$ 的堆上；在编号为 $N$ 的堆上取的纸牌，只能移到编号为 $N-1$ 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

题目分析

首先定义 $\texttt{avg}$ 为纸牌总数的平均数。如果要使每堆纸牌的数量一样多的话，那么经过移动后要使 $A_i=\texttt{avg}$。

对于第一堆牌，它只能由第二堆牌进行索取，或者进行给予。设 $x=A_i-\texttt{avg}$。如果 $x>0$，那么就把多的给第二堆。如果 $x<0$，不管怎么移动，必然有一步是第二堆给第一堆 $\lvert x \rvert$ 张牌。上述两种情况答案需要加 $1$。如果 $x=0$，就不用管了。

此时我们发现第一堆牌已经符合条件了，那么第一堆就可以直接忽略了，此时第二堆就变成了第一堆，继续重复上述步骤。

如何说明这样做是最优的呢？我们发现在上述过程中，每一步都是必须的，没有多余的步骤，所以其必然是最优解，这也是贪心思想的体现。

如果移牌的过程中出现负数怎么办？对于这个问题，可以发现移牌的步骤的顺序不是固定的，这样，我们就可以每次移动不会出现负数的牌堆，这样的方案是一定存在的。

代码

#include<iostream>
using namespace std;
int n,a[100001],sum,s,ans;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	sum/=n;
	for(int i=0;i<n-1;i++)
	{
		if(a[i]!=sum)
		{
			a[i+1]+=(a[i]-sum);
			ans++;
		}
	}
	cout<<ans;
    return 0;
}