1320:【例6.2】均分纸牌(Noip2002) 2020-11-30

简介: 1320:【例6.2】均分纸牌(Noip2002) 2020-11-30

1320:【例6.2】均分纸牌(Noip2002)

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

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

a1a2…an (n 堆纸牌,每堆纸牌初始数,l≤ai≤10000)。

【输出】

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

【输入样例】

4

9 8 17 6

【输出样例】

3

1. #include <iostream>
2. #include <cstdio>
3. #include <algorithm>
4. using namespace std;
5. int a[105];
6. int main(int argc, char *argv[])
7. {
8.  int n,sum=0;
9.  scanf("%d",&n);
10.   for(int i=1;i<=n;i++){
11.     scanf("%d",&a[i]);sum+=a[i];
12.   }
13.   int tmp=sum/n;
14.   for(int i=1;i<=n;i++)a[i]-=tmp;
15.   int i=1,j=n;
16.   sum=0;
17.   while(a[i]==0&&i<n)i++;
18.   while(a[j]==0&&j>1)j--;
19.   while(i<j){
20.     a[i+1]+=a[i];
21.     a[i]=0;
22.     sum++;
23.     i++;
24.     while(a[i]==0&&i<j)i++;
25.    }
26.   printf("%d\n",sum);
27.   return 0;
28. }
29. /*
30. 注意: 
31. 1.善于将每堆牌数减去平均数,简化了问题;
32. 2.要过滤掉0(不是所有的0,如一2,3,0,-1中的0是不能过滤的);
33. 3.负数张牌也可以移动,这是关键中的关键。*/

 

相关文章
|
7月前
|
Java
leetcode-452:用最少数量的箭引爆气球
leetcode-452:用最少数量的箭引爆气球
74 0
|
6月前
|
人工智能 程序员 定位技术
老程序员分享:NOIP2016天天爱跑步(树上差分)
老程序员分享:NOIP2016天天爱跑步(树上差分)
35 0
|
7月前
|
Serverless
P1149 [NOIP2008 提高组] 火柴棒等式
P1149 [NOIP2008 提高组] 火柴棒等式
|
7月前
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
45 0
|
算法 Java
代码随想录算法训练营第三十四天 | LeetCode 860. 柠檬水找零、406. 根据身高重建队列、452. 用最少数量的箭引爆气球
代码随想录算法训练营第三十四天 | LeetCode 860. 柠檬水找零、406. 根据身高重建队列、452. 用最少数量的箭引爆气球
70 0
|
定位技术 C++
洛谷P1600 [NOIP2016 提高组] 天天爱跑步
洛谷P1600 [NOIP2016 提高组] 天天爱跑步
leetcode 452用最少数量的箭引爆气球
leetcode 452用最少数量的箭引爆气球
93 0
leetcode 452用最少数量的箭引爆气球
(数论)蓝桥杯AcWing 1205. 买不到的数目
(数论)蓝桥杯AcWing 1205. 买不到的数目
56 0