干草

2022春季每日一题 and USACO

题目链接

https://www.acwing.com/problem/content/2050/
关于这题的题号是Oler们庆祝日的2倍.....

题目描述

奶牛们又来捣乱了！

农夫约翰精心整理的 $N$ 堆干草，每堆干草的高度相同。

但是，奶牛们趁着他不注意在干草堆之间移动了一些干草捆，使得各个干草堆的高度可能不再相同了。

给定所有干草堆的新高度，请帮助约翰确定，为了使所有干草堆恢复到原来的相同高度，至少要移动的最小干草捆数。

输入格式

第一行包含整数 $N$。

接下来 $N$ 行，每行包含一个整数（范围 [$1$,$1000$]），表示每个干草堆的现有干草捆数量（也就是新高度）。

输出格式

输出需要移动的最小干草捆数。

数据范围

$1≤N≤10000$

样例

输入样例：

4
2
10
7
1

输出样例：

7

样例解释

至少要移动 $7$ 个干草捆（将 $3$ 个干草捆从第 $2$ 堆移动至第 $1$ 堆，将 $2$ 个干草捆从第 $2$ 堆移动至第 $4$ 堆，将 $2$ 个干草捆从第 $3$ 堆移动至第 $4$ 堆）。

算法

方法十分简单

先求出这些干草的平均值，它们的平均值就是目标值

然后小于平均值的就把它和平均值的差累加就可以了

大于等于平均值的不用管它

c++代码

#include<iostream>
using namespace std;
long long n,a[10100],sum,cnt;
int main()
{
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        cnt+=a[i];
    }
    cnt=cnt/n;//求出平均值
    for(long long i=1;i<=n;i++)
    {
        //如果小于平均值就代表需要移动
        if(a[i]<cnt) sum+=cnt-a[i]; 
    }
    printf("%lld",sum);
}