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 的大小
• 如果 sum mod n 不等于 0，则 -
  • 返回 -1
• req := sum / n, ret := 0, extra := 0
• 初始化 i := 0，当 i < n 时，更新（将 i 增加 1），执行 -
  • x := v[i]
  • extra := extra + (x - req)
  • 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

Arnab Chakraborty

更新于: 2020-06-01

484 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习