मान लीजिए कि हमारे पास एक पंक्ति में n सुपर वाशिंग मशीन हैं। प्रारंभ में, प्रत्येक वॉशिंग मशीन में कुछ कपड़े या खाली होते हैं। अब, प्रत्येक चाल के लिए, हम कोई भी m (1 m ≤n) वाशिंग मशीन चुन सकते हैं, और साथ ही साथ प्रत्येक वॉशिंग मशीन की एक ड्रेस उसके बगल की वाशिंग मशीन को दे सकते हैं। मान लीजिए कि हमारे पास पंक्ति में बाएं से दाएं प्रत्येक वॉशिंग मशीन में कपड़े की संख्या का प्रतिनिधित्व करने वाला एक पूर्णांक सरणी है, तो हमें सभी वाशिंग मशीनों में समान संख्या में कपड़े बनाने के लिए न्यूनतम चालें मिलनी चाहिए। अगर ऐसा करना संभव न हो तो -1 को वापस कर दें।
तो जब इनपुट [1,0,5] की तरह है, तो आउटपुट 3 होगा, ऐसा इसलिए है क्योंकि 5 से 0 भेजें, इसलिए वितरण [1, 1, 4] होगा, फिर मध्य 1 से बाएं एक, 4 1 तक, फिर यह [2,1,3] होगा, फिर 2 से 1, तो अंत में यह [2,2,2]
होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- योग :=v के सभी तत्वों का योग
- n :=v का आकार
- यदि योग mod n 0 के बराबर नहीं है, तो −
- वापसी -1
- अनुरोध:=योग / एन, सेवानिवृत्त:=0, अतिरिक्त:=0
- इनिशियलाइज़ i :=0 के लिए, जब i
- x :=v[i]
- अतिरिक्त :=अतिरिक्त + (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