假设我们连续有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