haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

均分纸牌

发布时间:2013-12-18 11:35:59  

[问题描述]

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

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

现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4,4 堆纸牌数分别为:

① 9 ② 8 ③ 17 ④ 6

移动3次可达到目的:

从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10)。

[输 入]:

键盘输入文件名。文件格式:

N(N 堆纸牌,1 <= N <= 100)

A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000)

[输 出]:

输出至屏幕。格式为:

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

[输入输出样例]

a.in:

4

9 8 17 6 屏慕显示:

3

分析:如果你想到把每堆牌的张数减去平均张数,题目就变成移动正数,加到负数中,使大家都变成0,那就意味着成功了一半!拿例题来说,平均张数为10,原张数9,8,17,6,变为-1,-2,7,-4,其中没有为0的数,我们从左边出发:要使第1堆的牌数-1变为0,只须将-1张牌移到它的右边(第2堆)-2中;结果是-1变为0,-2变为-3,各堆牌张数变为0,-3,7,-4;同理:要使第2堆变为0,只需将-3移到它的右边(第3堆)中去,各堆牌张数变为0,0,4,-4;要使第3堆变为0,只需将第3堆中的4移到它的右边(第4堆)中去,结果为0,0,0,0,完成任务。每移动1次牌,步数加1。也许你要问,负数张牌怎么移,不违反题意吗?其实从第i堆移动-m张牌到第i+1堆,等价于从第i+1堆移动m张牌到第i堆,步数是一样的。

如果张数中本来就有为0的,怎么办呢?如0,-1,-5,6,还是从左算起(从右算起也完全一样),第1堆是0,无需移牌,余下与上相同;再比如-1,-2,3,10,-4,-6,从左算起,第1次移动的结果为0,-3,3,10,-4,-6;第2次移动的结果为0,0,0,10,-4,-6,现在第3堆已经变为0了,可节省1步,余下继续。

程序清单

program NOIPG1;

const maxn=100;

var i,j,n,step:integer;ave:longint;

a:array[1..maxn]of integer;

f:text;filename:string;

begin

write('Input filename:');readln(filename);

assign(f,filename);reset(f);

readln(f,n);ave:=0;step:=0;

for i:=1 to n do begin

read(f,a[i]); inc(ave,a[i]);{读入各堆牌张数,求总张数ave}

end;

ave:=ave div n;{求牌的平均张数ave}

for i:=1 to n do a[i]:=a[i]-ave; {每堆牌的张数减去平均数}

i:=1;j:=n;

while (a[i]=0) and (i<n) do inc(i);{过滤左边的0}

while (a[j]=0) and (j>1) do dec(j);{过滤右边的0}

while (i<j) do begin

inc(a[i+1],a[i]);{将第i堆牌移到第i+1堆中去}

a[i]:=0;{第i堆牌移走后变为0}

inc(step);{移牌步数计数}

inc(i);{对下一堆牌进行循环操作}

while (a[i]=0) and (i<j) do inc(i);{过滤移牌过程中产生的0}

end;

writeln(step);

end.

点评:基本题(较易) 本题有3点比较关键:一是善于将每堆牌数减去平均数,简化了问题;二是要过滤掉0(不是所有的0,如-2,3,0,-1中的0是不能过滤的);三是负数张牌也可以移动,这是辩证法(关键中的关键)。

上一篇:砝码称重
下一篇:过河卒
网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com