首页 > 学院 > 开发设计 > 正文

P1031 均分纸牌

2019-11-14 12:48:12
字体:
来源:转载
供稿:网友

题目描述

n堆纸牌,用最少的移动次数使每堆纸牌数都一样多。

样例输入

49 8 17 6

样例输出

3

思路

O(2l)计算出平均值,把多的那堆纸牌推向少的那堆纸牌。var i,j,k,l,z,x,w,r,s:longint; a:array[1..100] of longint;begin readln(l); for i:=1 to l do begin read(a[i]); k:=k+a[i]; if x<a[i] then begin x:=a[i];z:=i;end; end; k:=k div l; while 1=1 do begin w:=0;r:=0; if x=k then break; for i:=1 to z-1 do w:=w+a[i]; if (z-1)*k-w>0 then begin a[z-1]:=a[z-1]+((z-1)*k-w);a[z]:=a[z]-((z-1)*k-w);inc(s);end; for i:=z+1 to l do r:=r+a[i]; if (l-z)*k-r>0 then begin a[z+1]:=a[z+1]+((l-z)*k-r);a[z]:=a[z]-((l-z)*k-r);inc(s);end; x:=0; for i:=1 to l do if x<a[i] then begin x:=a[i];z:=i;end; end; writeln(s);end.
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表