c++当雪人部落遇到了食物匮乏的季节会拿出储备粮接济吃不饱饭的雪人家庭。现在雪人部落中有n个家庭每个家庭有自己的储备粮数量。雪人部落会计算当前所有雪人家庭储备粮的平均值然后额外提供一些粮食给予低于平均值的雪人家庭使其粮食储量达到计算的平均值。请问雪人部落一共需要提供多少储备粮。输入 共两行。第一行为一个整数nn=105表示有n个雪人家庭。第二行为n个整数表示每个雪人家庭的储备粮数量。输出 一个数表

算法1

(暴力枚举) $O(n)$

先对所有家庭的储备粮求和，再求平均值，最后再遍历一遍，统计需要提供的储备粮的数量。

时间复杂度

统计和，遍历数组，所以时间复杂度是$O(n)$。

C++ 代码

算法2

(排序算法) $O(n \log n)$

首先对所有家庭的储备粮进行降序排序，计算总的储备粮的和，遍历家庭储备粮数组，当家庭储备粮小于平均值时，这个家庭需要额外提供的数量就是平均值与当前家庭储备粮数的差值，然后统计需要的储备粮。

时间复杂度

排序算法的复杂度是$O(n\log n)$，计算和和遍历数组，所以时间复杂度是$O(n)$。

C++ 代码