均分纸牌 #

1. 均分纸牌的介绍
2. 均分纸牌的算法分析
3. 均分纸牌的代码实现

均分纸牌的介绍 #

有N堆纸牌，编号分别为1,2,……n。每堆上有若干张,但纸牌总数必为n的倍数.可以在任一堆上取若干张纸牌,然后移动。
移牌的规则为：在编号为1上取的纸牌,只能移到编号为2的堆上,在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上。其他堆上取的纸牌，可以移到相邻左边或右边的堆上。能否找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如：n=4, 4堆纸牌分别为：(1):9 (2)8 (3)17 (4)6 移动三次可以达到目的：
1.从(3)取4张牌放到(4)
2.从(3)区3张放到(2)
3.从(2)去1张放到(1)

均分纸牌的算法分析 #

卡牌只能左右移动，我们首先将最左边的卡牌堆用最小的次数，移动到平均值，再将剩下卡牌最左边的卡牌堆用最小的次数，移动到平均值，依次类推，直到所有的卡牌堆都为平均数
如第i堆的纸牌数不等于平均值v,则移动一次,分两种情况移动：
1．若a[i]>v，则将a[i]-v张从第i堆移动到第i+1堆；
2．若a[i]<v，则将v-a[i]张从第i+1堆移动到第i堆。
为了设计的方便，我们把这两种情况统一看作是将a[i]-v从第i堆移动到第i+1堆，移动后有a[i]=v; a[i+1]=a[i+1]+a[i]-v.
在从第i+1堆取出纸牌补充第i堆的过程中可能会出现第i+1堆的纸牌小于零的情况。
如n=3，三堆指派数为1 2 27 ，这时v=10，为了使第一堆为10，要从第二堆移9张到第一堆，而第二堆只有2张可以移，按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的，我们在移动过程中，只是改变了移动的顺序，而移动次数不变。

均分纸牌的代码实现 #

n=int(input())#输入纸牌堆数
a=[int(i) for i in input().split()]#输入每堆纸牌个数
v=sum(a)//n 
s=0 #移动次数
while(len(a)!=0 and a[0]==v):a.pop(0)#过滤最左边的平均数
while(len(a)!=0 and a[-1]==v):a.pop()#过滤最右边的平均数
while(len(a)!=0):#仍有需要过滤的纸牌堆
    a[1]=a[0]+a[1]-v
    a[0]=v
    s=s+1 #每次移动次数加一
    while (len(a)!=0 and a[0]==v): a.pop(0)##每次移动后将最左边的平均数过滤掉
print(s)#输出结果

小结 #

• 根据均分纸牌，理解贪心算法
• 掌握均分纸牌求解的贪心算法，能够根据实际问题作出合适的贪心策略

习题 #

1. 用自己的语言描述上述均分卡牌问题的子问题
2. 如果不限制卡牌的相邻移动，试求解卡牌均分问题的最小次数