資料結構
網路
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 次瀏覽
廣告