Cho n máy giặt trên hàng, mỗi máy có số áo. Mỗi bước chọn tập máy, mỗi máy chuyển 1 áo sang máy lân cận. Tìm số bước tối thiểu để mọi máy có cùng số áo. Không thể thì -1.
Ví dụ
[1,0,5] → 3. Bước 1: máy 3→2: [1,1,4]. Bước 2: máy 2→1, 3→2: [2,1,3]. Bước 3: máy 1→2: [2,2,2].
Quan sát quan trọng
Số áo trung bình avg = sum/n (phải nguyên). Số bước = max của: (số áo dư/thiếu tại mỗi máy), (tích lũy dư/thiếu từ trái sang).
Chương trình C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMinMoves(vector<int>& v) {
int sum = accumulate(v.begin(), v.end(), 0);
int n = v.size();
if(sum % n != 0) return -1;
int avg = sum / n;
int ans = 0, balance = 0;
for(int x : v) {
balance += x - avg;
ans = max({ans, x - avg, abs(balance)});
}
return ans;
}
};
int main() {
Solution ob;
vector<int> v = {2,1,6};
cout << ob.findMinMoves(v); // 3
return 0;
}