題目
You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.
For each move, you could choose any m (1 ≤ m ≤ n) 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 representing the number of dresses in each washing machine from left to right on the line, you should find 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 -1.
Example1
Input: [1,0,5]
Output: 3
Explanation:
1st move: 1 0 <-- 5 => 1 1 4
2nd move: 1 <-- 1 <-- 4 => 2 1 3
3rd move: 2 1 <-- 3 => 2 2 2
Example2
Input: [0,3,0]
Output: 2
Explanation:
1st move: 0 <-- 3 0 => 1 2 0
2nd move: 1 2 --> 0 => 1 1 1
Example3
Input: [0,2,0]
Output: -1
Explanation:
It's impossible to make all the three washing machines have the same number of dresses.
答案
思考的方法
題目說每個move可以同時把很多個洗衣機的一件衣服往左或者往右移動
如果你直接去想怎么移動才能使得所有洗衣機包含同樣數(shù)量的衣服，很難想出一個辦法來
但是如果你假設(shè)題目所給出的移動方法可以使你用最少的步數(shù)達(dá)到平衡(每個洗衣機衣服數(shù)量相等)如筛，然后再去思考在最好的情況下粘秆，用多少步就能達(dá)到平衡，這樣或許會更容易找到答案迁筛。
代碼
class Solution {
public int findMinMoves(int[] machines) {
int sum = 0, balance = 0, moves = 0, target = 0, n = machines.length;
for(int x : machines) sum += x;
if(sum % n != 0) return -1;
target = sum / machines.length;
for(int i = 0; i < n; i++) {
int left = 0;
if(balance < 0) {
left = -balance;
moves = Math.max(moves, left);
}
balance += (machines[i] - target);
if(balance > 0)
moves = Math.max(moves, balance + left);
}
return moves;
}
}
