计算在搬动最小轮数的前提下，使每个机器上的物品数量相等的解析

问题描述

        有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打 包机上，放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人 将每个机器上的物品进行移动从而到达物品数量相等才能打包。每个物品重量太大、 每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。请计算在搬动最小轮数的前提下，使每个机器上的物品数量相等。如果不能使每个机器上的物品相同， 返回-1。

        例如[1,0,5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后:
                第一轮:1 0 <- 5 => 1 1 4

                第二轮:1 <- 1 <- 4 => 2 1 3

                第三轮:2 1 <- 3 => 2 2 2
                移动了3轮，每个机器上的物品相等，所以返回3
        例如[2,2,3]表示有3个机器，每个机器上分别有2、2、3个物品， 这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1。

思路

        首先我们判断机器上的物品总数是否可以平分到各个机器上去。把每个机器上的物品总数相加除以机器数，若结果为整数即可以平分到各个机器上，并且结果为平分都各机器上的物品数量，若结果有余数则表示不可以平分到各个机器上，直接返回-1即可。

        我们选取机器其中一个机器X进行分析，把机器X左侧记为左半部分，右侧记为右半部分。我们可以计算出左半部分比预期超出（或不足）的数量用 leftRest 表示，同理右半部分用 rightRest 表示。我们分析可以得出共有四种情况的发生。

        情况一：leftRes > 0 , rightRest > 0 。表示左侧部分和右侧部分均需要向机器X移动物品，此时机器X的最小轮数为 leftRes 和 rightRest 两者之间的最大值。

        情况二：leftRes > 0 , rightRest < 0 。 表示左侧部分需要向机器X移动物品，右侧部分需要从机器X上向右移动物品，此时机器X的最下轮数为 leftRes 和 rightRest的绝对值两者之间的最大值。

        情况三：leftRes < 0 , rightRest > 0 。 表示右侧部分需要向机器X移动物品，左侧部分需要从机器X上向左移动物品，此时机器X的最下轮数为 leftRes的绝对值 和 rightRest两者之间的最大值。

        情况四：leftRes < 0 , rightRest < 0 。 表示左侧部分和右侧部分均需要从机器X向左右两部分移动物品，此时机器X的最下轮数为 leftRes的绝对值 和 rightRes的绝对值t两者之和。

        情况一、二、三综合一下可得：机器X的最下轮数为 leftRes的绝对值 和 rightRest的绝对值两者之间的最大值。

代码

    public static int machine(int[] arr){
        if (arr==null || arr.length==0){
            return -1;
        }
        int size = arr.length;
        int sum = 0;
        for (int i =0;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
            int leftRest = leftSum -i*avg;
            int rightRest = (sum - leftSum - arr[i]) - (size -i-1)*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;
    }