当前位置：首页 > article >正文

算法之物品移动

article 2024/12/23 19:30:24

算法之

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. 思路

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

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

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

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));
    }
}