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.负数张牌也可以移动,这是关键中的关键。*/

 

相关文章
|
5月前
|
人工智能 算法 BI
AcWing 505. 火柴排队(每日一题)
AcWing 505. 火柴排队(每日一题)
|
10月前
|
Java
leetcode-452:用最少数量的箭引爆气球
leetcode-452:用最少数量的箭引爆气球
87 0
|
9月前
[NOIP2002]过河卒 标准递归
[NOIP2002]过河卒 标准递归
53 6
|
9月前
|
人工智能 程序员 定位技术
老程序员分享:NOIP2016天天爱跑步(树上差分)
老程序员分享:NOIP2016天天爱跑步(树上差分)
45 0
|
9月前
|
搜索推荐 算法 C++
蓝桥杯分糖果、最小化战斗力差距、小蓝零花钱
这是一个关于算法问题的集合,包括三个不同的任务: 1. **分糖果**:肖恩有不同种类的糖果要分给学生,目标是使得到糖果字符串的字典序最大且尽量小。给定糖果种类数和一个初始字符串,输出能达到的最小字典序的最大值。 2. **最小化战斗力差距**:小蓝需要将队员分为两组,每组战斗力差距最小。给定队员数量和战斗力值,找出最小的战斗力差距。 3. **小蓝的零花钱**:小蓝要在序列中分割偶数和奇数,每次分割代价是两端元素差的绝对值。目标是在预算内确定最多能进行多少次这样的分割。 每个问题都提供了输入输出示例和相应的C++代码片段来解决这些问题。
|
9月前
【洛谷 P1002】[NOIP2002 普及组] 过河卒 题解(递归+记忆化搜索)
`NOIP2002`普及组的过河卒问题是一个棋盘路径计数挑战。卒从$(0,0)$出发到$(n,m)$,只能向下或向右移动,马在$(c1,c2)$固定,控制某些点。任务是计算不受马阻挡的路径数。输入是目标和马的位置,输出是路径总数。使用动态规划和记忆化搜索避免重复计算,样例输入$(6,6,3,3)$输出$6$。代码中定义了$f(x,y)$计算$(x,y)$处的路径数,利用边界条件和递推关系计算。
103 0
1314:【例3.6】过河卒(Noip2002)
1314:【例3.6】过河卒(Noip2002)
175 0
|
算法
每日一题冲刺大厂第十七天 逆序对
大家好,我是泡泡,给大家带来每日一题的目的是为了更好的练习算法,我们的每日一题为了让大家练到各种各样的题目,熟悉各种题型,一年以后,蜕变成为一个不一样的自己!
307 0
leetcode 452用最少数量的箭引爆气球
leetcode 452用最少数量的箭引爆气球
100 0
leetcode 452用最少数量的箭引爆气球
|
算法
【递归与递推】洛谷[NOIP2002 普及组] 过河卒
前言 本题来自洛谷P1002. 题目链接:[NOIP2002 普及组] 过河卒 - 洛谷
262 0

热门文章

最新文章