13.均分纸牌

【问题描述】

有 N 堆纸牌&＃xff0c;各堆编号分别为 1&＃xff0c;2&＃xff0c;…, N。每堆上有若干张纸牌&＃xff0c;但所有纸牌总数必为 N 的整数倍。可以在任一堆上取若干张纸牌&＃xff0c;然后按如下规则进行移动&＃xff1a;
在编号为 1 堆上取的纸牌&＃xff0c;只能移到编号为 2 的堆上&＃xff1b;在编号为 N 的堆上取的纸牌&＃xff0c;只能移到编号为 N-1 的堆上&＃xff1b;其他堆上取的纸牌&＃xff0c;可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法&＃xff0c;用最少的移动次数使每堆上纸牌数都一样多。
例如 N&＃61;4&＃xff0c;4 堆纸牌数分别为&＃xff1a;　　①　9　②　8　③　17　④　6
移动3次可达到目的&＃xff1a;

1. 从 ③ 取 4 张牌放到 ④&＃xff08;9 8 13 10&＃xff09;


2. 从 ③ 取 3 张牌放到 ②&＃xff08;9 11 10 10&＃xff09;


3. 从 ② 取 1 张牌放到 ①&＃xff08;10 10 10 10&＃xff09;


【输入文件】

从当前目录下的card.in文件中取得输入。输入文件格式&＃xff1a;
第一行为一个整数N&＃xff08;N 堆纸牌&＃xff0c;1 <&＃61; N <&＃61; 100&＃xff09;&＃xff1b;
第二行为N个整数A1 A2 … An &＃xff08;N 堆纸牌&＃xff0c;每堆纸牌初始数&＃xff0c;l<&＃61; Ai <&＃61;10000&＃xff09;。
【输出文件】

输出文件card.out只有一行&＃xff0c;包含一个整数&＃xff0c;表示最少移动次数。
【输入样例】

4
9 8 17 6
【输出样例】

3
【样例说明】

4堆纸牌最少移动3次使每堆的纸牌数一样多。

f &＃61; open(&＃39;card.in&＃39;)
line &＃61; f.readline()
list_line &＃61; [line] # 储存读入的文件&＃xff0c;只读入前两行
m &＃61; 2
while m > 1:line &＃61; f.readline()list_line.append(line)m -&＃61; 1
n &＃61; list_line[0].replace(&＃39;\n&＃39;, &＃39;&＃39;) # 获取N
list_card &＃61; list_line[1].split() # 获取堆
sm &＃61; 0
list_cards &＃61; []
for i in list_card: # 求和sm &＃43;&＃61; int(i)list_cards.append(int(i)) # int值储存
average &＃61; int(sm / int(n)) # 获取平均数
t &＃61; 0
count &＃61; 0
for i in range(int(n)): # 遍历每个牌堆# 如果这个牌堆收到移动过来的牌数后不等于平均数&＃xff0c;就需要移动if list_cards[i] &＃43; t !&＃61; average:# 计算移动的牌数&＃xff0c;或正或负t &＃61; list_cards[i] &＃43; t - average# 计数count &＃43;&＃61; 1else:t &＃61; 0 # 不用移动就是移动0张且次数不变
g &＃61; open(&＃39;card.out&＃39;, &＃39;a&＃39;)
g.seek(0) # 定位头位置
g.truncate() # 从头位置清空文件内容
g.write(str(count)) # 写入文件
f.close()
g.close()