C++의 슈퍼 세탁기

<시간/>

n개의 슈퍼 세탁기가 한 줄에 있다고 가정해 봅시다. 처음에는 각 세탁기에 드레스가 있거나 비어 있습니다. 이제 각 이동에 대해 m(1 ≤ m ≤ n) 세탁기를 선택하고 각 세탁기의 드레스 하나를 인접한 세탁기 중 하나로 전달할 수 있습니다. 행의 왼쪽에서 오른쪽으로 각 세탁기의 드레스 수를 나타내는 하나의 정수 배열이 있다고 가정하면 모든 세탁기가 동일한 수의 옷을 갖도록 최소 이동 수를 찾아야 합니다. 할 수 없으면 -1을 반환합니다.

따라서 입력이 [1,0,5]와 같을 때 출력은 3이 됩니다. 이것은 5를 0으로 보내기 때문이므로 분포는 [1, 1, 4]가 되고 중간 1에서 왼쪽 1, 4가 됩니다. 1로 변경하면 [2,1,3]이 되고 2에서 1이 되므로 마지막으로 [2,2,2]

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

sum :=v의 모든 요소의 합
n :=v의 크기
합계 mod n이 0이 아닌 경우 -
- 반환 -1
req :=합계 / n, ret :=0, 추가 :=0
초기화 i의 경우:=0, i
x :=v[i]
추가 :=추가 + (x - 필수)
ret :=최대 {ret, x - req, |extra|

반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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));
}

입력

{2,1,6}