均分纸牌

题目描述：

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

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

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

分析：

所有堆均达到相等时的最少移动次数。

一看到最少这个字眼，就应该想到贪心或者动态规划。

而我的思路是：

因为题目上说：

纸牌总数必为N的倍数

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

所以我就想：那么我用每堆的纸牌数去减掉平均数，不就是这堆纸牌需要多少张牌才满足题目条件吗？

又因为：

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

所以，如果这堆的纸牌数>0，我们就需要将它的多余纸牌移动到纸牌数<0的纸牌堆上去。

反之，如果这堆的纸牌数<0，我们就需要将它的缺少的纸牌从纸牌数>0的纸牌堆上移动到它上去。

于是，有了思路，代码打起来也就非常简单了。

代码实现：

#include<iostream>

#include<cmath>

using namespace std;

int n;//纸牌堆数

int a[10005];//储存纸牌数

int num=0;//纸牌的平均数

int ans=0;//移动次数

int flag=1;//表示纸牌不需要移动

int main()

{

	cin>>n;//输入纸牌堆数

	for(int i=1;i<=n;i++)

	{

		cin>>a[i];//输入每堆的纸牌数

		num+=a[i];//纸牌的总数进行累加

	}

	num/=n;//num变为总纸牌数的平均数

	for(int i=1;i<=n;i++) a[i]-=num;//将每堆纸牌数变为距离满足条件的纸牌数的数

	for(int i=1;i<=n;i++) if(a[i]!=0) flag=0;//flag==0，表明需要移动

	if(flag==0)//需要移动，那么就开始吧！

	{

		for(int i=1;i<=n;i++)//从头遍历到尾

		{

			if(a[i]>0)//如果它的纸牌数多了

			{

				a[i+1]+=a[i];//就把它移动到下一堆去

				a[i]=0;//这一堆满足条件

				ans++;//移动次数++

			}

			if(a[i]<0)//如果它的纸牌数少了

			{

				a[i+1]-=abs(a[i]);//那么它下一堆的纸牌就移动到它上来

				a[i]=0;//这一堆满足条件

				ans++;//移动次数++

			}

			if(a[i]==0) continue;//如果它满足条件，就不鸟它了。

		}

		cout<<ans<<endl;//输出答案

	}

	if(flag==1) cout<<ans<<endl;//如果本来就满足条件，直接输出答案（0）

	return 0;

}

巴特西

【题解】P1440 均分纸牌

均分纸牌

分析：

代码实现：

最新文章

热门文章