移动次数最少(贪心)

移动次数最少

时间限制: 1 Sec  内存限制: 128 MB

题目描述

有n堆糖果（2≤n≤200），排成一行，编号分别为1,2,…n。
已知每堆糖果有一定的颗数，且颗数之和均为n的倍数。移动各堆中的任意颗糖果，使每堆的数量达到相同，且移动次数最少。
  移动规则：
  每次可以移动任意的糖果颗数，第1堆可以移向第2堆，第2堆可以移向第1堆或第3堆,。。。。。。 第n 堆只可以移向第n -1堆。
例如，当n=4时：
堆号      1     2     3     4 
颗数      9     8     17    6
移动的方法有许多种， 其中的一种方案：
① 第3堆向第4堆移动4颗，成为：9    8    13    10
② 第3堆向第2堆移动3颗，成为：9    11   10    10
③ 第2堆向第1堆移动1颗，成为：10   10   10    10
经过三次移动，每堆都成为10颗。

输入

有两行。
第一行一个整数n。
第二行n个整数，用空格分隔。

输出

一个整数（表示最少移动次数）。

样例输入

复制样例数据

4
9　8　17　6

样例输出

3

贪心，每次将当前少的或多的通过后面一堆来满足，最后一堆根本不用管，因为肯定已经满足了（总的糖果刚好可以整除）。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
int a[205];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	int sum = 0;
	for (int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		sum += a[i];
	}
	int ans = 0;
	sum /= n;
	for (int i = 1; i < n; i++){
		int t = sum - a[i];
		if(!t) continue;
		a[i + 1] -= t;
		ans++;
	}
	printf("%d\n", ans);

	return 0;
}
/**/