AcWing 每日一题 2022/5/2【2048. 干草】

奶牛们又来捣乱了! 农夫约翰精心整理的 N 堆干草,每堆干草的高度相同。 但是&#…

奶牛们又来捣乱了!

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

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

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

输入格式
第一行包含整数 N。

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

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

数据范围

1≤N≤10000

输入样例:

输出样例:

样例解释
至少要移动 7 个干草捆(将 3 个干草捆从第 2 堆移动至第 1 堆,将 2 个干草捆从第 2 堆移动至第 4 堆,将 2 个干草捆从第 3 堆移动至第 4 堆)。

题目分析

先看给定的范围大小 104
确定时间复杂度为O(n)或者O(nlogn)
看完题目大水体,直接模拟即可
在读入的时候,可以直接计算出平均值
然后进行一次排序,只要将小于平均值的数值全部改变为平均值后,相对应的大于平均值的数值就会变为平均值

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/3571.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部