Skip to content

Latest commit

 

History

History

517.Super-Washing-Machines

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

517.Super-Washing-Machines

此题初看会有一种用DP的错觉.但细细想一想,其实最优策略是可以手工制定出来的,这就是贪心法.

首先,我们应该有这样的直觉,对任意一台洗衣机,最优的转移策略肯定不会出现"反反复复"的情况.即经过充分的优化调度后,衣物的转移应该是单向的.假设对于第i台洗衣机,最终平衡态是k件,设整个过程中i总共向左边净转移了left[i]件衣物,向右边净转移了right[i]件衣物,则必定满足如下关系:

machines[i]-k = left[i]+right[i]

并且在实际的最优操作中,第i台一定只需要向左移动left[i]件衣物,向右移动right[i]件衣物即可(注意,这两个值可能是负数)。总之同一个边不会有多余的双向操作。

其次,我们把所有洗衣机的初始状态想象成一座连绵起伏的山峦。每一次move前,我们知道哪些山峰是净输出的,哪些山谷是净输入的,而这一次move的效果就是:将某些山峰的一件衣物“超距作用”地转移到某些山谷中去。所谓的“超距作用”,就是说这种山峰填山谷的操作只需要一个回合就能完成。这是因为每个回合所有的洗衣机都在同时工作,每个洗衣机只有三种作用:净输出1,净值为0,净输入1或者2(某个山谷同时由两边来填)。那些净值为0的洗衣机其实就相当于传送带,某一边输入一件,同时又往另一边输出一件,从而协助了山峰填山谷的超距作用。

很显然,整批洗衣机需要停止工作的回合,就是等到那些山峰最终夷为平地的时刻。所以最终答案,就是找到“总输出”最多的那台机器即可。为什么是要算总输出呢?因为有可能是这种情景:左边的次山峰->主山峰->填补谷底。这样的一个回合,主山峰其实并没有净输出,是次山峰在净输出。但我们可以想象,主山峰一定是在不停地输出(不一定是净输出),而当主山峰不输出了,说明肯定一切都已经夷为平地了。

至于如何确定left[i]和right[i]是比较简单的,突破口就是最左边的洗衣机,其left[i]一定是零;次外,所有的right[i]=-left[i+1]。故这些变量都可解。

Leetcode Link