亿万先生:标题陈说 Description

1098 均分卡片

 

二〇〇二年NOIP全国联赛提升组

 时间限制: 1
s

 空间限制: 128000KB

 题目品级 : 白金Gold

题解

 

 

 

标题陈说 Description

有 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)。

输入描述 Input Description

第一行N(N 堆纸牌,1 <= N <= 100)
其次行A1 A2 … An (N 堆卡牌,每堆卡牌伊始数,l<= Ai <=一千0)

出口描述 Output Description

输出至显示屏。格式为:
抱有堆均达到格外时的起码运动次数。‘

样例输入 萨姆ple Input

4
9 8 17 6

样例输出 Sample Output

3

数码范围及提醒 Data Size & Hint

e

思路:

假让你想到把每堆牌的张数减去平均张数,标题就造成移动正数,加到负数中,使大家都变成0,那就代表成功了大意上!拿例题来讲,平均张数为10,原张数9,8,17,6,变为-1,-2,7,-4,当中并未有为0的数,我们从侧面出发:要使第1堆的牌数-1变为0,只须将-1张牌移到它的左侧(第2堆)-第22中学;结果是-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步,余下继续。

 

亿万先生: 1亿万先生: 2

 1 #include<iostream>
 2 using namespace std;
 3 int a[10001];
 4 int tot=0;
 5 int ans;
 6 int main()
 7 {
 8     int n;
 9     cin>>n;
10     for(int i=1;i<=n;i++)
11     {
12         cin>>a[i];
13         tot=tot+a[i];
14     }
15     tot=tot/n;
16     for(int i=1;i<=n;i++)
17     {
18         a[i]=a[i]-tot;
19     }
20     for(int i=1;i<=n;i++)
21     {
22         if(a[i]==0)continue;
23         else
24         {
25             a[i+1]=a[i+1]+a[i];
26             a[i]=0;
27             ans++;
28         }
29     }
30     cout<<ans;
31     return 0;
32 }

View Code

 

 

 

相关文章

网站地图xml地图