USACO Dec11 Hay Bales 原題、翻譯、題解

【英文原題】
Problem 1: Hay Bales [Brian Dean, 2011]

The cows are at it again!  Farmer John has carefully arranged N (1 <= N <=
10,000) piles of hay bales, each of the same height.  When he isn't
looking, however, the cows move some of the hay bales between piles, so
their heights are no longer necessarily the same.  Given the new heights of
all the piles, please help Farmer John determine the minimum number of hay
bales he needs to move in order to restore all the piles to their original,
equal heights.

PROBLEM NAME: haybales

INPUT FORMAT:

* Line 1: The number of piles, N (1 <= N <= 10,000).

* Lines 2..1+N: Each line contains the number of hay bales in a single
        pile (an integer in the range 1...10,000).

SAMPLE INPUT (file haybales.in):

4
2
10
7
1

INPUT DETAILS:

There are 4 piles, of heights 2, 10, 7, and 1.

OUTPUT FORMAT:

* Line 1: An integer giving the minimum number of hay bales that need
        to be moved to restore the piles to having equal heights.

SAMPLE OUTPUT (file haybales.out):

7

OUTPUT DETAILS:

By moving 7 hay bales (3 from pile 2 to pile 1, 2 from pile 2 to pile 4, 2
from pile 3 to pile 4), we can make all piles have height 5.

【中文翻譯】
USACO美國信息學月賽 2011年12月賽  銅組 
Problem 1: 乾草堆

奶牛們又來了!農夫約翰成功地準備了N(1<=N<=10,000)捆乾草，每捆乾草都有相同的高度。然而，當他不注意的時候

，他的奶牛們在兩捆乾草之間移動了一部分乾草，所以這些乾草的數量不再和以前一樣了。

給你每捆乾草新的數量，請幫助農夫約翰計算出他最少需要移動多少乾草，使每捆都恢復到初始時的數量，也就是那個

相同的數量。

程序名稱：haybales

輸入格式：

*第1行：乾草的捆數N(1<=N<=10,000)。

*第2~1+N行，每行包含一個整數，表示第i捆乾草的數量，（一個1、10,000之間的整數）。

輸入樣例(file haybales.in)：

4
2
10
7
1

輸入解釋：

一共有4捆乾草，它們的高度分別是2,10,7和1。

輸出格式：

* 第一行：一個整數，表示至少需要移動多少乾草，
才能使每捆乾草恢復到相等的高度。

輸出樣例(file haybales.out)：

7

輸出解釋：
移動7份乾草（把3份乾草從第2捆移至第一捆，把2份乾草從第2捆移至第4捆，把2份乾草從第3捆移至第4捆），我們就

可以把每捆乾草的高度都變成5。
 【分析】
 貪心就可以了，也是【NOIP2002提高組 均分紙牌】的這種類型。
先統計出平均數，再計算出 每捆乾草數量與平均數的差值（的絕對值）之和，然後除以2即可。

時間複雜度：O(N*2)
空間複雜度：N

【我的代碼】

1	/*
2	ID:yeefan
3	LANG:C++
4	PROB:haybales
5	*/
6	#include <iostream>
7	#include <cstdio>
8	#include <cstdlib>
9	using namespace std;
10	int N;
11	int A[10001];
12	long long Sum=0;
13	long long Avg=0;
14
15	int abs(int x)
16	{
17	if(x<0)
18	x=-x;
19	return x;
20	}
21
22	void init()
23	{
24	scanf("%d\n",&N);
25	for (int i=1;i<=N;i++)
26	{
27	scanf("%d\n",&A[i]);
28	Avg+=A[i];
29	}
30	Avg/=N;
31	}
32
33	void work()
34	{
35	for (int i=1;i<=N;i++)
36	{
37	Sum+=abs(A[i]-Avg);
38	}
39	cout<<Sum/2<<endl;
40	}
41
42	int main()
43	{
44	freopen("haybales.in","r",stdin);
45	freopen("haybales.out","w",stdout);
46	init();
47	work();
48	return 0;
49	}