sjtuoj 3016. 均分纸牌 贪心

缘起

日常浪费生命~ sjtuoj 3016. 均分纸牌

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
【问题描述】　　
有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张
纸牌，然后移动。　　移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取
的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。　　现在要求找出一
种移动方法，用最少的移动次数使每堆上纸牌数都一样多。　　例：若 N=4，4 堆纸牌数分别为：8　7　16　5　　
移动3次可达到目的：　　从第三堆取4张牌放到第四堆（8 7 12 9）->从第三堆取3张牌放到第二堆（8 10 9 
9）->从第二堆取1张牌放到第一堆（9 9 9 9）。

【输 入】
输入数据包括2行　　第一行是整数N，表示N 堆纸牌（1 <= N <= 100）　　A1 A2 … An （N 堆纸牌，每堆纸
牌初始数，l<= Ai <=10000）

【输 出】　　
输出整数M，为所有堆均达到相等时的最少移动次数。

【输入输出样例】

输入  
4
8 7 16 5    

输出
3
【数据规模】
100%的数据满足：1<=N<=100  1<=Ai<=10000

这么看这道题——从左边第一堆开始一直到第N-1堆. 每堆纸牌都要通过它右边的堆去凑ave（平均数），如果恰好等于ave的话，则不需要移动，如果不等，则需要通过它右边堆的纸牌来凑ave. 例如一堆纸牌张数为4，ave=4，则总的移动次数不变. 如果<ave, 例如为3， 则需要问它右边的堆借一张纸牌，产生的移动次数+1. 如果>ave, 例如是7张，则也要产生移动，问右边的堆借-3张纸牌. 产生的移动次数也要+1. 所以最少移动次数不会超过n-1. 有没有可能<n-1呢? 完全可能~ 只要上述过程中出现纸牌张数=ave的情况移动次数就不增加了呀~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int n, a[105];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d", &n);
	int tot = 0,ave;
	for (int i = 0; i<n; i++)
	{
		scanf("%d", a+i);
		tot+=a[i];
	}
	ave = tot/n; // 输入保证n能整除tot
	int ans = 0;
	for (int i = 0; i<n-1; i++)
	{
		if (a[i]==ave)
		{
			continue;
		}
		a[i+1]+=(a[i]-ave);
		ans++;
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

运行编号 提交者 题目编号 评测结果 分数 时间 内存 语言 提交时间
684304 yfsyfsyfs 3016 正确 100 3ms 4492kb C++ 2019-09-19 06:45:00