[LeetCode]Super Washing Machines

这道题我们可以观察出几点，假设我们有n台洗衣机：

1. 如果衣服的总数不能被n整除，显然我们不能做到；如果能做到，每台机器最终被分配的衣服数量是固定的，假设为k
2. 以处在i的机器为界，根据k，我们可以算出从[0 : i]流向[i + 1 : n - 1]的衣服数量m1；同时，我们也可以算出需要从[i : n - 1]流向[0 : i - 1]的数量m2，m1 + m2就是机器i需要被选择的总次数m
3. 算出所有机器的m，求最大值即可

时间复杂度O(n)，空间O(1)，代码如下：

	class Solution {
	public:
	int findMinMoves(vector<int>& machines) {
	int n = machines.size(), sum = 0, maxMove = 0;
	for(auto& machine : machines)sum += machine;
	if(sum % n)return -1;
	int k = sum / n, preSum = 0;
	for(int i = 0; i < n; ++i)
	{
	int toLeft = 0, toRight = 0;
	if(i > 0)
	toLeft = k * i - preSum > 0? k * i - preSum: 0;
	if(i < n - 1)
	toRight = (n - i - 1) * k - (sum - preSum - machines[i]) > 0?
	(n - i - 1) * k - (sum - preSum - machines[i]): 0;
	preSum += machines[i];
	maxMove = max(maxMove, toRight + toLeft);
	}
	return maxMove;
	}
	};

view raw Super Washing Machines.cpp hosted with ❤ by GitHub