Giả sử chúng ta có n siêu máy giặt trên một hàng. Ban đầu, mỗi máy giặt có một số áo dài hoặc trống. Bây giờ, đối với mỗi lần di chuyển, chúng ta có thể chọn m (1 ≤ m ≤ n) máy giặt bất kỳ và chuyển một bộ quần áo của mỗi máy giặt sang một trong các máy giặt liền kề của nó cùng một lúc. Giả sử chúng ta có một mảng số nguyên đại diện cho số lượng quần áo trong mỗi máy giặt từ trái sang phải trên hàng, chúng ta nên tìm số movesto tối thiểu để tất cả các máy giặt có cùng số lượng quần áo. Nếu không thể thực hiện, hãy trả về -1.
Vì vậy, khi đầu vào giống như [1,0,5], thì đầu ra sẽ là 3, điều này là do gửi 5 đến 0, vì vậy phân phối sẽ là [1, 1, 4], sau đó giữa 1 sang trái một, 4 thành 1, sau đó sẽ là [2,1,3], sau đó là 2 thành 1, vì vậy cuối cùng sẽ là [2,2,2]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- sum:=tổng tất cả các phần tử của v
- n:=kích thước của v
- nếu tổng mod n không bằng 0, thì -
- trả về -1
- req:=sum / n, ret:=0, extra:=0
- để khởi tạo i:=0, khi i
- x:=v [i]
- extra:=extra + (x - req)
- ret:=tối đa là {ret, x - req, | extra |
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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 req = sum / n;
int ret = 0;
int extra = 0;
for(int i = 0; i < n; i++){
int x = v[i];
extra +=( x - req);
ret = max({ret, x - req, abs(extra)});
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,1,6};
cout << (ob.findMinMoves(v));
} Đầu vào
{2,1,6} Đầu ra
3