super-washing-machines

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You have <code>n</code> super washing machines on a line. Initially, each washing machine has some dresses or is empty.

For each move, you could choose any <code>m</code> (<code>1 &lt;= m &lt;= n</code>) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time.

Given an integer array <code>machines</code> representing the number of dresses in each washing machine from left to right on the line, return the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return <code>-1</code>.

&nbsp;
Example 1:

<pre>
Input: machines = [1,0,5]
Output: 3
Explanation:
1st move: 1 0 &lt;-- 5 =&gt; 1 1 4
2nd move: 1 &lt;-- 1 &lt;-- 4 =&gt; 2 1 3
3rd move: 2 1 &lt;-- 3 =&gt; 2 2 2
</pre>

Example 2:

<pre>
Input: machines = [0,3,0]
Output: 2
Explanation:
1st move: 0 &lt;-- 3 0 =&gt; 1 2 0
2nd move: 1 2 --&gt; 0 =&gt; 1 1 1
</pre>

Example 3:

<pre>
Input: machines = [0,2,0]
Output: -1
Explanation:
It&#39;s impossible to make all three washing machines have the same number of dresses.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == machines.length</code></li>
	<li><code>1 &lt;= n &lt;= 104</code></li>
	<li><code>0 &lt;= machines[i] &lt;= 105</code></li>
</ul>

findMinMoves

Super Washing Machines

Greedy

Array

假设有 <code>n</code>&nbsp;台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 <code>m</code> (<code>1 &lt;= m &lt;= n</code>) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个整数数组&nbsp;<code>machines</code> 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 <code>-1</code> 。

&nbsp;

示例 1：

<pre>
输入：machines = [1,0,5]
输出：3
解释：
第一步: 1 0 &lt;-- 5 =&gt; 1 1 4
第二步: 1 &lt;-- 1 &lt;-- 4 =&gt; 2 1 3 
第三步: 2 1 &lt;-- 3 =&gt; 2 2 2 
</pre>

示例 2：

<pre>
输入：machines = [0,3,0]
输出：2
解释：
第一步: 0 &lt;-- 3 0 =&gt; 1 2 0 
第二步: 1 2 --&gt; 0 =&gt; 1 1 1 
</pre>

示例 3：

<pre>
输入：machines = [0,2,0]
输出：-1
解释：
不可能让所有三个洗衣机同时剩下相同数量的衣物。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == machines.length</code></li>
	<li><code>1 &lt;= n &lt;= 104</code></li>
	<li><code>0 &lt;= machines[i] &lt;= 105</code></li>
</ul>