制作网站价格,php图片网站源码,千锋教育官方网,手机网站设计机构P1031 均分纸牌 题目描述 有 N 堆纸牌#xff0c;编号分别为 1#xff0c;2#xff0c;…, N。每堆上有若干张#xff0c;但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌#xff0c;然后移动。 移牌规则为#xff1a;在编号为 1 堆上取的纸牌#xff0c;只能移到… P1031 均分纸牌 题目描述 有 N 堆纸牌编号分别为 12…, N。每堆上有若干张但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌然后移动。 移牌规则为在编号为 1 堆上取的纸牌只能移到编号为 2 的堆上在编号为 N 的堆上取的纸牌只能移到编号为 N-1 的堆上其他堆上取的纸牌可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法用最少的移动次数使每堆上纸牌数都一样多。 例如 N44 堆纸牌数分别为 ①9②8③17④6 移动3次可达到目的 从 ③ 取 4 张牌放到 ④ 9 8 13 10 - 从 ③ 取 3 张牌放到 ②9 11 10 10- 从 ② 取 1 张牌放到①10 10 10 10。 输入输出格式 输入格式 键盘输入文件名。文件格式 NN 堆纸牌1 N 100 A1 A2 … An N 堆纸牌每堆纸牌初始数l Ai 10000 输出格式 输出至屏幕。格式为 所有堆均达到相等时的最少移动次数。 输入输出样例 输入样例#14
9 8 17 6输出样例#13 说明 noip2002提高组 这是一道很简单的贪心题。 i表示第i个牌堆每次都保证i牌堆是等于平均纸牌 因为如果这堆牌少那么肯定要从别的牌堆借(可以让下一堆牌暂时负数) 这堆牌多肯定要扔去别的牌堆。 那么我们当前只考虑该牌堆的牌是否等于平均纸牌(贪心) 如果多余就扔去下一个牌堆如果少就从下一个牌堆借(下一个牌堆表示mdzz)。 这样弄下去保证了1到n-1的牌堆是等于平均牌数那么第n堆牌也等于平均牌数。 1 #include cstdio2 3 int main()4 {5 int n, a[105], sum, ans;6 sum ans 0;7 scanf(%d, n);8 for(int i1; in; i) //第i堆牌从1开始到n9 {
10 scanf(%d, ai);
11 sum a[i];
12 }
13
14 sum / n; //计算平均牌数
15 for(int i1; in; i)
16 {
17 if(a[i] ! sum) //如果不等于
18 {
19 if(a[i] sum) //大于就扔多于的
20 {
21 a[i1] a[i] - sum; //重置下一个牌堆数量
22 a[i] sum;
23 ans; //次数1
24 }
25 else //小于就拿少于的
26 {
27 a[i1] - sum - a[i]; //重置下一个牌堆数量
28 a[i] sum;
29 ans;
30 }
31 }
32 }
33
34 printf(%d, ans);
35 return 0;
36 } 转载于:https://www.cnblogs.com/yBaka/p/7375195.html
