数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究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
更新于: 2020-06-01
484 次浏览
广告