每天一道算法题11

【机器打包问题】
有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打包机上，放到每个机器
上的这些物品数量有多有少，由于物品数量不相同，需要工人将每个机器上的物品进行移动从而达到物品数量相等才能
打包，每个物品质量太大。每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动，请计算在搬动最小轮数的情况
下，使每个机器上的物品数量相等，如果不能使每个机器上物品相同，返回-1，例如[1,0,5]表示有3个机器，每个机器
上有1，0，5 个物品，需要经过3次移动，可使的每个机器上物品相等。

解答：这题假设第i个物品，左边总共有left1，达到相等时应该有left2，则要搬出去的数量为left1-left2,同样，右边总共
有right1,达到相等时应该有right2，则要搬出去的数量为right1-right2, 如果两边都小于0，说明i这个机器物品太多，需要移动的数量为
二者绝对值之后，如果一个为正，一个为负，则i在往负数机器运输的同时，别的机器也可以往i机器运输。则需要移动的数量为绝对值较大的那个。
那最少移动次数为各个i该情况下最大的那个。即只要满足了最困难的那个i，其他的都能满足，那这个就为最小移动次数。

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 < arr.length; i++) {
        int leftRes = leftSum - i * avg;
        int rightRes = sum - leftSum - arr[i] - (size - i - 1) * avg;
        if (leftRes < 0 && rightRes < 0) {
            ans = Math.max(ans, Math.abs(leftRes) + Math.abs(rightRes));
        } else {
            ans = Math.max(ans, Math.max(Math.abs(leftRes), Math.abs(rightRes)));
        }
        leftSum += arr[i];
    }
    return ans;
}