C++のスーパー洗濯機

連続してn台のスーパー洗濯機があるとします。最初に、各洗濯機はいくつかのドレスを持っているか、空です。これで、移動ごとに、任意のm（1≤m≤n）の洗濯機を選択し、各洗濯機の1つのドレスを隣接する洗濯機の1つに同時に渡すことができます。行の左から右に各洗濯機のドレスの数を表す1つの整数配列があるとすると、すべての洗濯機に同じ数の衣服を持たせるための最小移動数を見つける必要があります。それが不可能な場合は、-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
• x：=v [i]
• extra：=extra +（x --req）
• 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}

出力

3