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:= sum / n,ret:= 0,extra:= 0

  • 对于初始化i:= 0,当i <n时,更新(将i增加1),执行-

    • x:= v [i]

    • 额外:=额外+(x-要求)

    • ret:= {ret,x-req,| extra |的最大值

  • 返回ret

让我们看下面的实现以更好地理解-

示例

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

输出结果

3