517. Super Washing Machines

https://leetcode.com/problems/super-washing-machines/

https://leetcode-cn.com/problems/super-washing-machines/solution/

看了官方的题解,但是没有搞明白为什么这么计算是最优的,不过这个计算过程对于培养直觉可能还有点帮助。

我觉得这个解释有点意思 https://leetcode.com/problems/super-washing-machines/discuss/369787/topic

首先求出最终的目标target,如果没有最终目标,直接返回-1.

对于每个洗衣机,我们计算他需要移走多少衣服(负数表示他需要获得多少衣服)从任意一边开始计算,比如从左边:

第一个洗衣机如果移走了衣服,那么肯定移给了他右边的洗衣机,所以右边的洗衣机在遍历时,要加上左边需要移走的;
如果一个洗衣机需要移来衣服,他也是从右边的洗衣机获得,右边的洗衣机需要移来的衣服也是要加上左边的,故over这个变量要一直加下去。
而且,他为负就表示从右边索要,他为正,说明左边来的已经超出了需要,转移给右边。

对于任何一个洗衣机,如果他需要移走的衣服是正数,最终移动的数量肯定要大于这个数(显然),如果是负数,就不用大于他的绝对值了(因为可以从两边移动到这里)。
而对于自己本来就比目标大的,最终移动的次数一定大于自己衣服减去目标数,因为不管是左边需要,还是右边需要,对于这个洗衣机,每次都最多只能出一个。
这个最终移动的下界就是答案(他存在吗?存在,只要按照我们遍历的顺序去做,按照over指示的去做就可以达到)

有点像之前二叉树上面去分摊均匀的一道题目,题号不记得了。

可以考虑一下:

或许没有办法证明是最优的,但是始终这种类似直觉的思想解决问题,至少得到个相对较优解还是不错的。

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        S = sum(machines)
        n = len(machines)
        if S % n != 0:
            return -1
        avg = S // n
        acc = 0
        ans = 0
        for x in machines:
            adjust = x - avg
            acc += (x - avg)
            ans = max(ans, adjust, abs(acc))
        return ans

解答里面提到而二叉树均摊问题在这里 https://leetcode.com/problems/distribute-coins-in-binary-tree/. 这个明显没有想象的难,因为所有的挪动都是顺序完成的。 我们只需要考虑某个子树需要收入/分发出多少个coin即可,从部分考虑最终得到整体。

class Solution:
    def distributeCoins(self, root: TreeNode) -> int:
        ans = 0

        def pre(root: TreeNode):
            if root is None:
                return 0, 0

            lc, lv = pre(root.left)
            rc, rv = pre(root.right)
            return lc + rc + 1, lv + rv + root.val

        count, total = pre(root)
        if total % count != 0:
            return -1
        avg = total // count

        def visit(root):
            nonlocal ans
            if root is None:
                return 0, 0

            lc, lv = visit(root.left)
            rc, rv = visit(root.right)
            c = lc + rc + 1
            v = lv + rv + root.val
            if v != c * avg:
                delta = abs(v - c * avg)
                ans += delta
            return c, v

        visit(root)
        return ans