算法之物品移动

算法之

1. 题目

有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打包机上，放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人 将每个机器上的物品进行移动从而到达物品数量相等才能打包。每个物品重量太大、 每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。请计算在搬动最小轮数的前提下，使每个机器上的物品数量相等。如果不能使每个机器上的物品相同， 返回﹣1。
例如［1,0,5］表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后：
第一轮：1 0 <-5 => 114 第二轮：1<-1<-4 =>2 1 3 第三轮：2 1<-3=>2 2 2移动了3轮，每个机器上的物品相等，所以返回3
例如［2,2,3］表示有3个机器，每个机器上分别有2、2、3个物品，这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回﹣1。

2. 解释

就是说，让物品在相邻的打包机器之间移动，但是每次只能移动一个，不过可以同时多个进行移动。

3. 思路

我们进行移动，肯定是有一个方向的，不能一个往左，一个往右，这样相当于没有移动。假设以当前的这个机器为节点，它的左右进行移动。
有三种情况：

1. 当前的机器上的包裹少，两边都多，那么，包裹就会向当前机器上流动。当前情况下，移动的次数是包裹最多的一侧向当前机器移动的次数。另一侧的移动会跟这一侧的移动同时进行。
2. 当前机器包裹多，两边都少，那么包裹会从当前机器向两边移动。当前情况下，因为包裹只能移动一个，所以移动次数是两侧差多少包裹的和
3. 一侧包裹多，一侧包裹少，包裹从一侧移向另一侧。这时，移动次数等于，少的一侧缺少的数量与多的一侧多的数量的最大值。

我们接下来进行循环，计算每一个位置的移动次数，求最少。

4. 代码

public class Code02_PackingMachine {
    public static int MinOps(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int size = arr.length;
        int sum = 0;
        for(int i = 0; i < size; i++){
            sum += arr[i];
        }
        if(sum % size != 0){
            return -1;
        }
        int avg = sum / size;
        int leftSum = 0;
        int ans = 0;
        for(int i = 0; i < size; i++){
            int leftRest = leftSum - i * avg;
            int rightRest = (sum - leftSum) - (size - 1 - i) * avg;
            if(leftRest < 0 || rightRest < 0){
                ans = Math.max(ans, Math.abs(leftRest) + Math.abs(rightRest));
            }else{
                ans = Math.max(ans, Math.max(Math.abs(leftRest), Math.abs(rightRest)));
            }
            leftSum += arr[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        System.out.println(MinOps(arr));
    }
}

运行结果为

3

5. 总结

很简单