空间限制,标题叙述 Description

1098 均分纸牌

 

2002年NOIP全国联赛升高组

 时间限制: 1
s

 空间范围: 128000
KB

 题目等级 : 黄金
高尔德

题解

 

 

 

标题叙述 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 <=10000)

出口描述 Output Description

出口至显示屏。格式为:
装有堆均达到卓殊时的最少运动次数。‘

样例输入 Sample 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堆)-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步,余下继续。

 

图片 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

 

 

 

1098 均分纸牌

 

2002年NOIP全国联赛升高组

 时间限制: 1
s

 空间范围: 128000
KB

 标题等级 : 黄金
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 <=10000)

输出描述 Output Description

输出至显示器。格式为:
持有堆均达到出色时的最少运动次数。‘

样例输入 Sample 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堆)-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步,余下继续。

 

图片 3图片 4

 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地图