8. 摆平积木

时间限制：1.000S 空间限制：32MB

题目描述

小明很喜欢玩积木。一天，他把许多积木块组成了好多高度不同的堆，每一堆都是一个摞一个的形式。然而此时，他又想把这些积木堆变成高度相同的。但是他很懒，他想移动最少的积木块来实现这一目标，你能帮助他吗？

输入描述

输入包含多组测试样例。每组测试样例包含一个正整数n，表示小明已经堆好的积木堆的个数。 接着下一行是n个正整数，表示每一个积木堆的高度h，每块积木高度为1。其中1<=n<=50,1<=h<=100。 测试数据保证积木总数能被积木堆数整除。 当n=0时，输入结束。

输出描述

对于每一组数据，输出将积木堆变成相同高度需要移动的最少积木块的数量。 在每组输出结果的下面都输出一个空行。

输入示例

6

5 2 4 1 7 5

0

输出示例

5

解法一(模拟)

思路分析:

1. 模拟题意进行输入与输出;
2. 对于移动最少积木, 即移动积木时, 从高于平均高度的积木移走积木到低于平均高度的积木堆, 即只需算出每堆积木与平均高度的差再除2即可;

实现代码如下:

public class k_8_LevelTheBlocks {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = 0;
        int[] nums = new int[51];
        while (in.hasNext() && ((n = in.nextInt()) != 0)) {
            int sum = 0;
            int result = 0;
            for (int i = 0; i < n; ++ i) {
                nums[i] = in.nextInt();
                sum += nums[i];
            }
            int average = sum / n;
            for (int i = 0; i < n; ++ i) {
                result += Math.abs(nums[i] - average);
            }
            System.out.println(result/2);
            System.out.println();
        }
    }
}

运行结果如下:

运行时间： 597ms 消耗内存： 21336kb

复杂度分析:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$